Connected $𝒌$-Median with Disjoint and Non-Disjoint Clusters

This lemma is proved by contradiction. Assume that ${(x_v^c)}_{v\in V,c\in C}$ is a solution for LP (2.1) that violates some constraint of LP (2.1). Then there exist two terminals $u,v\in T_c$ and an $(u,v)$-cut $S$ such that

Now we distinguish two cases. In the first case let $c$ be one of the nodes $\{u,v\}$, w.l.o.g. $u=c$. Then we can use the definition of LP (2.1) and $T_c$ to obtain

which contradicts the assumption.

In the second case both $u\ne c$ and $v\ne c$. Then by the previous argument $S$ can neither separate $u$ nor $v$ from $c$ because then its weight would be at least $1$. Thus there exists a path from $u$ to $c$ and from $c$ to $v$ not containing any nodes in $S$. But then there also exists a path from $u$ to $v$ not using any nodes in $S$ and $S$ would not be a $(u,v)$-cut. $◀$

This lemma is crucial because for the node weighted Steiner tree problem there exists an $O(\log n)$-approximation algorithm by Klein and Ravi [15] for which Guha et al. [11] later proved that it is implicitly a primal-dual algorithm and that the cost of the solution is at most $O(\log n)$ times worse than any fractional solution of LP (2.1). Alternatively Könemann et al provided a more detailed primal-dual algorithm for a generalized version of the node weighted Steiner tree problem ensuring the same guarantees [16]. Using these algorithms and Lemma 12 we are able to subdivide $x$ into $k$ Steiner tree LP solutions that can each be transformed into a feasible cluster.

In the first step of the algorithm we will first calculate an optimum solution $\tilde{x}$ for the relaxed version of LP (2.1) which as argued above can be done in polynomial time. Since every assignment solution for the connected $k$-median problem is also an LP solution, the costs of $\tilde{x}$ are upper bounded by the optimum value OPT. After multiplying the values by $k$, the cost of solution $x$ is then again bounded by $k\cdot \text{OPT}$.

Consider $T_c$ as defined above, by Markov’s inequality for every node $v$ there exists a center $c$ such that ${\tilde{x}}_v^c\ge \frac{1}{k}$ which means that $v\in T_c$. Thus we have ${\bigcup }_{c\in C}{T}_c=V$. By Lemma 12 the fractional solution $x$ can be split up into $k$ solutions of the Steiner tree LP (2.1) with the respective terminal sets ${\left(T_c\right)}_{c\in C}$ such that the total sum of the objective value is exactly the cost of $x$.

By applying the algorithm by Klein and Ravi [15] with $T=T_c$ and $w(v)=d(v,c)$ for every $c\in C$ separately, one obtains a Steiner tree $S_c$ with $T_c\subseteq S_c$ whose cost is upper bounded by $O(\log n)$ times the cost of the respective LP solution. Thus one obtains in polynomial time $k$ Steiner trees each connecting the respective terminal set $T_c$ and total cost bounded by $O(\log n)$ times the objective value of $x$ which results in an upper bound of $O\left(k\log n\right)\text{OPT}$. Since every node is contained in at least one of these Steiner trees, this directly yields the desired solution for the assignment version of the non-disjoint connected $k$-median problem.

This proof works even if the distances are not a metric because it does not use any of their properties. $◀$

One may note that this approach works with any approximation algorithm for the node weighted Steiner tree problem whose cost is bounded by the optimum LP solution. For some restricted graph classes, including planar graphs, Demaine et al. [5] provided a primal dual algorithm calculating a constant approximation. Thus the approach can also be used to get an $O(k)$-approximation (and $O(k^2)$ if the centers are not given) for these kind of connectivity graphs.

To obtain half-opened centers, let an optimal (fractional) LP solution $\tilde{x}$ be given. For each $v$, let its mass be defined as $m_v={\sum }_{c\in V}{\tilde{x}}_v^c$, its cost (or price) as $p_v={\sum }_{c\in V}{\tilde{x}}_v^c\cdot d(v,c)$ and its (average) radius as $r_v=\frac{p_v}{m_v}$. We say that an assignment of a node $v$ to another node $c$ is good if $d(v,c)\le 4r_v$. Since $m_v\ge 1$ for all nodes $v\in V$, we may observe that because of Markov’s inequality at least $\frac{3}{4}$ of $v$ gets assigned via good assignments, i.e., ${\sum }_{c\in V:d(v,c)\le 4r_v}{\tilde{x}}_v^c\ge \frac{3}{4}$.

We will simultaneously maintain two assignments ${(x_v^c)}_{v,c\in V}$ and ${(y_v^c)}_{v,c\in V}$ such that for all $v,c\in V$ initially $x_v^c={\tilde{x}}_v^c$ and $y_v^c=0$ and that at the end of the algorithm $x_v^c=0$. The final values of $y_v^c$ will be the assignment using half opened centers. During the algorithm, the combination of $x$ and $y$ will always be a $\frac{1}{8k}$-connected solution, which means that the following inequalities stay satisfied throughout the entire process:

The algorithm will now maintain an initially empty center set $C$ and repeat in an alternating order the following two steps: First it decides for an additional node whether it gets added to the center set or not (in the latter case it will be added to a so called environment of an already existing center). Afterwards it shifts some openings in $x$ (the $x_c^c$ that are greater than $0$) to already chosen centers $c$ in $C$.

To get an intuition regarding the shifts, it can be beneficial to sometimes think about the connectivity constraints not from a cut-perspective but to rather interpret the assignments as flows. Using the max-flow min-cut theorem, it is easy to see that if we interpret the values ${(x_{v^{\prime }}^{c^{\prime }})}_{v^{\prime }\in V}$ as node capacities then there exists a flow from a node $v$ to a node $c^{\prime }$ of value $f$ exactly if ${\text{sep}}^x(v,c^{\prime })\ge f$. Thus our connectivity constraint implies that there always exists a flow from $v$ to $c^{\prime }$ of value $x_v^{c^{\prime }}$. By basically reverting this flow for a center $c\in C$ and a node $c^{\prime }\in V$ we are able to shift an opening of value $x_c^{c^{\prime }}$ from $c^{\prime }$ to $c$. One important question is now how the nodes that were previously assigned to $c^{\prime }$ get assigned. If $x_c^{c^{\prime }}$ was equal to $x_{c^{\prime }}^{c^{\prime }}$, the entire opening of $c^{\prime }$ can be shifted and we can simply reassign all nodes to $c$ by setting $y_v^c=y_v^c+x_v^{c^{\prime }}$ and $x_v^{c^{\prime }}=0$ for any $v\in V$. However, if $x_c^{c^{\prime }}$ was smaller than $x_{c^{\prime }}^{c^{\prime }}$ only a fraction of the opening of $c^{\prime }$ gets shifted and we basically have to split up the previous assignments to $c^{\prime }$ between $c$ and $c^{\prime }$. As Figure 1 shows this can lead to situations in which the total assignment to $c$ and $c^{\prime }$ after this shift actually needs to be larger than the assignment before this shift. Since it is actually rather involved to determine the new values in this situation, a formal description will only be provided in the full version of this work. To get an intuition regarding the algorithm it is for now sufficient to only consider the first case.

Since either way also the assignments of nodes assigned to $c^{\prime }$ have to be shifted in this situation, we have to make sure that the distances of the respective shifts are not too large which the algorithm will ensure by only allowing shifts with a rather small distance between $c$ and $c^{\prime }$ in the beginning and increasing this distance over time. More details will follow later.

While the shifts depend on the chosen centers $C$, the choice whether a node $v$ will be added to $C$ in turn depends on the shifts that have already been performed before $v$ gets considered by the algorithm. The algorithm terminates once it has decided for every node whether it gets added to $C$ and all openings in $x$ have been shifted.

To determine which nodes should be added to $C$, we iterate over all nodes ordered by their radii in increasing order and check whether we can open them by at least $\frac{1}{2}$. To be more precise, a node $v$ will be chosen as a center if the sum of the remaining good assignments ${(x_v^{c^{\prime }})}_{c^{\prime }\in V}$ is at least $\frac{1}{2}$. The construction of the algorithm will ensure that it will shift at least all remaining openings belonging to good assignments of $v$ to $v$ itself which means that $v$ will be at least half opened. When $v$ is added to the center set we also create its environment $S_v=\{v\}$, which initially only contains $v$ itself.

In the case that $v$ does not get chosen as a center, we know that there were at least $\frac{1}{4}$ of good assignments of $v$ that have already been shifted to other centers in $C$. Since every center in $C$ gets at least half opened and the entire opening is limited by $k$, we know that $|C|\le 2k$ and thus there exists at least one center to which $\frac{1}{8k}$ of the good assignments of $v$ have been shifted. One critical property of the algorithm will be that before $v$ gets considered, the distance between the source $c^{\prime }$ and target $c$ of any shift will be at most $4r_v$. Thus for any good assignment to a node $z$ whose opening has been shifted to a center $c$ we have that $d(v,c)\le d(v,z)+d(z,c)\le 8r_v$. As a result we may conclude that there exists a center $c\in C$ such that $y_v^c\ge \frac{1}{8k}$ while $d(v,c)\le 8r_v$ and we add $v$ to the environment $S_c$ of the closest center $c$ fulfilling these requirements.

Adding $v$ to this environment allows us to shift some openings of a node $c^{\prime }$ with $x_v^{c^{\prime }}>0$ over the node $v$ to $c$ even if there does not exist a direct flow from $c$ to $c^{\prime }$ (i.e., $c$ is not assigned to $c^{\prime }$). The intuition behind this is that we first revert the flow from $v$ to $c^{\prime }$ and thus are already shifting the opening to $v$. Now by combining $y_v^c\ge \frac{1}{8k}$ and Property (7) we know that already before this shift the minimum cut between $v$ and $c$ has value at least $\frac{1}{8k}$. Thus if we are moving the opening (and the assignments to it) to $c$ instead of $v$ itself we know that the solution still stays $\frac{1}{8k}$-connected. Furthermore since $v$ and $c$ are not too far apart, we know that the distances of these shifts does not increase too much compared to a direct shift to $v$. This will help us ensuring that if the openings of some nodes, to which $v$ got assigned, get shifted to some other centers then the distance added by this shift will not be too large.

Every time after a new node $v$ gets added to either $C$ or to an environment $S_c$ of a center $c\in C$ we will go over all possible shifts ordered by their distances in increasing order, and perform all shifts with distance at most $4r_{\mathrm{next}}$, where $r_{\mathrm{next}}$ denotes the radius of the next node that will be considered by the algorithm. Note that any shift with radius $\le 4_{r_v}$ can only result from the addition of $v$ to $S_c$ or $C$ because any shift not involving $v$ would already have been applied in the last iteration (as $r_v$ is the previous value of $r_{next}$). As a result all those shifts will be performed before any shift not involving $v$ will be executed. This directly guarantees that if $v$ is added to $C$ then all openings belonging to good assignments will be shifted to $v$, which ensures that $v$ is half opened.

An important property of the shifts is that if we shift some opening of a node $c^{\prime }\in V$ over a node $v\in V$ then afterwards $x_v^{c^{\prime }}=0$ which ensures that for all $v,c^{\prime }\in V$ we will only shift some opening of $c^{\prime }$ over $v$ at most once, limiting the number of shifts by ${|V|}^2$. Additionally after we have added $v$ to $C$ or a set $S_c$ there always exists a possible shift while $x_v^{c^{\prime }}>0$ for a $c^{\prime }\in V$. Thus, it is possible to execute the described algorithm for a polynomial time until for every $v,c^{\prime }\in V$, $x_v^{c^{\prime }}=0$ and then return ${\left(y_v^c\right)}_{v\in V,c\in C}$. A pseudocode summarizing the structure of the described procedure can be found in Algorithm 1. The cost of the resulting $\frac{1}{8k}$-connected solution is bounded by $O(k)$ times the cost of the LP solution $\tilde{x}$.

Now we would like to reduce the number of centers to at most $k$. However, if we want to reduce the opening of a center $c\in C$ to $0$, we will need to find a suitable replacement, i.e., another center $\tilde{c}$ such that reassigning all nodes assigned to $c$ to $\tilde{c}$ neither costs too much nor violates our connectivity constraints (which is further relaxed to $\frac{1}{16k}$-connectivity). To do this we will need two properties of Algorithm 1:

• $\mathrm{■}$

  For any node $v$ we know that if a shift from another node $c^{\prime }$ to a center $c$ caused $v$ to be (partially) assigned to $c$ then the radius $r_c$ of $c$ can be bounded by the radius $r_v$ of $v$ and the distance from $v$ to $c^{\prime }$. To be more precise $r_c\le d(v,c^{\prime })+2r_v$. Intuitively, if this was not the case, then the algorithm would have shifted some opening of $c^{\prime }$ either to $v$ itself (if $v$ gets chosen as a center) or over $v$ to another center $\tilde{c}\in C$ with $v\in S_{\tilde{c}}$ before $c$ was even added to the center set which would have prevented $v$ from being assigned to $c$. The main consequence of this property is that if we can find another center $\tilde{c}$ that is only a constant times $r_c$ away from $c$ then reassigning all nodes that are currently assigned to $c$, to $\tilde{c}$ instead costs not too much.

• $\mathrm{■}$

  Additionally for any center $c$ it holds that if $c$ got assigned to another center $\tilde{c}$ because some opening got shifted from a node $c^{\prime }$ to $c$ then it holds that $d(c,\tilde{c})$ is bounded by $d(c,c^{\prime })+\max (4r_c,d(c,c^{\prime }))$ because otherwise a shift from $c^{\prime }$ to $c$ would have happened before the shift to $\tilde{c}$. Since the average length of the original assignments of $c$ was $r_c$, one can use this to identify a center $\tilde{c}$ that is not too far apart from $c$.

Using these two properties, we are able to split up $C$ into two sets $C_1$ and $C_{1/2}$ such that for every center $c\in C_{1/2}$ we have a successor $s(c)\in C$ such that the total cost that occurs if we replace any center in $C_{1/2}$ by its successor would not be too large and $|C_1|+\frac{1}{2}|C_{1/2}|\le k$. Later we will then open all nodes in $C_1$ as well as at most half the nodes in $C_{1/2}$ to obtain a integral center set $C^{\ast }$ such that for all nodes in $C_{1/2}$ either the node itself or its successor is contained in $C^{\ast }$.

To obtain these sets, we consider an arbitrary center $c\in C$ and define $a_c=1-y_c^c$. Then at least a total value of $a_c$ of the openings corresponding to the initial assignments of $c$ (the values ${\tilde{x}}_c^{c^{\prime }}$ for any $c^{\prime }\in V$) were shifted to other centers. If $a_c$ has value at least $\frac{1}{4}$, we are able to use Markov’s inequality together with the second property to identify another center $\tilde{c}$ such that $d(c,\tilde{c})$ lies within $O(r_c)$ and $c$ is already sufficiently connected to $\tilde{c}$ (i.e., $y_c^{\tilde{c}}\ge \frac{1}{16k}$). We thus can set $s(c)=\tilde{c}$ and add $c$ to $C_{1/2}$.

However, if $a_c$ is rather small then it can be that all assignments of $c$ to other centers $\tilde{c}$ only resulted from shifts of nodes $c^{\prime }$ to $\tilde{c}$ that are really far apart from $c$ which means that $\tilde{c}$ can be even further away. Additionally the assignments $y_c^{\tilde{c}}$ might also be quite small which means that we would need to increase some existing assignments to $\tilde{c}$ to ensure $\frac{1}{16k}$-connectivity if we replace $c$ by $\tilde{c}$. However, if there are multiple centers where the respective value $a_c$ is small then we know that since ${\sum }_{c\in C}(1-a_c)={\sum }_{c\in C}{y}_c^c\le k$ that if we add one of these centers to $C_{1/2}$ we can add multiple others to $C_1$. Since we do not need a replacement for the centers in $C_1$, we can use a careful potential argument to redistribute parts of the replacement cost of the centers added to $C_{1/2}$ to the centers in $C_1$ to bound the additional cost among all nodes.

To decide which centers in $C_{1/2}$ can be closed we have a look at the directed Graph $G_{1/2}=(C_{1/2},S)$, where $S=\{(c,s(c))\mid c,s(c)\in C_{1/2}\}$ contains for any center in $C_{1/2}$ an edge to its successor if the latter is again contained in $C_{1/2}$. If this graph is bipartite we can simply take the smaller half of this partition and add this to the center set $C^{\ast }$. Then for every edge one of its two endpoints is contained in $C^{\ast }$ which ensures that for every center either itself or its successor is contained in $C^{\ast }$. However, the graph might not directly be bipartite because it can contain cycles of uneven length. But we can ensure by being a little bit more careful in step 2 that any of these cycles contains at most one center $c$ with . Using this, we can remove the respective cycles and thus obtain a bipartite graph. For all centers in $C_{1/2}$ not added to $C^{\ast }$, we reassign all nodes assigned to them to the respective successor $s(c)$. Since we bounded the cost of replacing all centers in $C_{1/2}$ and are only replacing a subset of them, the total cost of this is again bounded. The entire cost still stays in $O(k)$ times the cost of the fractional LP solution $\tilde{x}$.

After step 3, we have an $\frac{1}{16k}$-connected solution only using integral centers. However the assignments might still be fractional. By multiplying the assignments by $16k$ the solution becomes $1$-connected and similarly as for the assignment version in Section 2.1 we obtain that for every node $v$ there exists at least one center $c$ such that $x_v^c\ge 1$. Again applying the primal dual algorithm for node weighted Steiner trees, we obtain an entirely integral solution: