Approximating $k$-Median via Pseudo-Approximation

Introduction

Suppose you wish to select $k$ polling stations for the US election so as to minimize the average distance each voter has to travel to his/her closest polling station. Then you need to solve the classic NP-hard $k$-median problem that we shall design better approximation algorithms for in this paper. Formally, a $k$-median instance $\mathcal{I}$ is defined by the tuple $(k,\mathcal{F},\mathcal{C},d)$, where $k$ is the number of facilities allowed to be opened, $\mathcal{F}$ is a set of potential facility locations, $\mathcal{C}$ is a set of clients, and $d$ is a distance metric over $\mathcal{F}\cup\mathcal{C}$. The goal is to open a set $\mathcal{S}\subseteq\mathcal{F}$ of $k$ facilities so as to minimize $cost_{\mathcal{I}}(\mathcal{S})=\sum_{j\in\mathcal{C}}d(j,\mathcal{S})$, where $d(j,\mathcal{S})$ denotes the distance from $j$ to its nearest facility in $\mathcal{S}$. When $\mathcal{F}=\mathcal{C}=X$, a solution $\mathcal{S}$ partitions the set of points into what is known as clusters and thus the objective measures how well $X$ can be partitioned into $k$ clusters. The $k$-median problem has numerous applications, starting from clustering and data mining to assigning efficient sources of supplies to minimize the transportation cost().

The difficulty of the $k$-median problem lies in the hard constraint that only $k$ facilities are allowed to be opened. Indeed, without such a constraint, we could simply open all facilities. Early approaches overcame this difficulty by giving pseudo-approximations that obtain better guarantees while violating the mentioned constraint by opening $k+\Omega(k)$ facilities. The first constant factor approximation algorithm that opens $k$ facilities is due to Charikar et al. . Based on LP rounding, their algorithm produces a $6\frac{2}{3}$-approximation. Several of the ideas in are inspired from constant factor approximation algorithms obtained for the closely related metric uncapacitated facility location (UFL) problem. The UFL problem has similar input as $k$-median but instead of giving an upper bound $k$ on the number of facilities we can open, it specifies an opening cost $f_{i}$ for each facility $i\in\mathcal{F}$. The goal is to open a set of facilities $\mathcal{S}$ that minimizes the sum of the opening costs and connection costs, i.e., $\sum_{i\in\mathcal{S}}f_{i}+\mathsf{cost}_{\mathcal{I}}(\mathcal{S})$.

The connection between UFL and $k$-median is motivated by basic economic theory: if we let the opening costs of facilities be small then a “good” solution to UFL will open many facilities whereas if we let the opening costs of facilities be large then a good solution will only open few facilities. By appropriately selecting the cost of facilities, one can therefore expect that an algorithm for UFL opens close to $k$ facilities and therefore almost also gives a solution to the $k$-median problem. This is the intuition of the concept of bi-point solutions that we define in Section 1.2. Jain and Vazirani first exploited this concept in a beautiful paper to obtain a $6$-approximation algorithm for $k$-median using their $3$-approximation primal-dual algorithm for UFL. The factor $3$ was later improved by Jain et al. to $2$ resulting in a $4$-approximation algorithm for $k$-median.

In spite of the apparent similarities between UFL and $k$-median, current techniques give a considerable better understanding of the approximability of UFL. For UFL and its variants, there has indeed been a steady stream of papers giving improved algorithms . The current best approximation algorithm is due to Li . He combined an algorithm by Byrka and an algorithm by Jain et al to achieve an approximation guarantee of $1.488$. This is close to being best possible, as it is hard to approximate UFL within a factor of $1.463$ . In contrast there has been less progress for $k$-median and the approximability gap is larger. The best known approximation algorithm is the local search algorithm given by Arya et al. . They showed that if there is a solution $\mathcal{F}^{\prime}$, where any $p$ swaps of the open facilities cannot improve the solution, then $\mathcal{F}^{\prime}$ is a $3+2/p$ approximation. This leads to a $3+\epsilon$ approximation that runs in time $n^{2/\epsilon}$. On the negative side, Jain et al. proved that the $k$-median problem is hard to approximate within a factor $1+2/e\approx 1.736$. Moreover, the natural linear programming relaxation of $k$-median is known to have an integrality gap of at least $2$. The best upper bound is by Archer et al. , who showed that the integrality gap is at most 3 by giving an exponential time rounding algorithm that requires to solve the maximum independent set problem.

As alluded to above, the main difficulty of the $k$-median problem is the hard constraint that we can open at most $k$ facilities. In this paper we take a different approach that allows us to relax this constraint and thereby addressing the problem from a novel point of view using what we call a pseudo-approximation algorithm. This leads to the improved approximation algorithm breaking the barrier of $3$ that we discuss next.

Our improved approximation algorithm can be stated as follows.

There is an algorithm which, given a $k$-median instance $\mathcal{I}$ and a number $\epsilon>0$, produces a $1+\sqrt{3}+\epsilon$-approximate solution to $\mathcal{I}$ in running time $O\left(n^{O(1/\epsilon^{2})}\right)$.

Our algorithm contains two main components, each of which, we believe, is of independent interest. First, we show that in order to give an approximation algorithm for $k$-median, it suffices to give a pseudo-approximation algorithm $\mathcal{A}$ which, given a $k$-median instance $\mathcal{I}$, outputs a set $\mathcal{S}\subseteq\mathcal{F}$ of $k+c$ facilities with $\mathsf{cost}_{\mathcal{I}}(\mathcal{S})\leq\alpha\mathsf{opt}_{\mathcal{I}}$, where $\mathsf{opt}_{\mathcal{I}}$ is the cost of optimum solution for $\mathcal{I}$. Given such an algorithm $\mathcal{A}$ as a black box, we can design an $\alpha+\epsilon$-approximation algorithm $\mathcal{A}^{\prime}$ whose running time is $n^{O(c/\epsilon)}$ times that of $\mathcal{A}$. Interestingly, the instance (see Figure 1) that gives the integrality gap of $2$ for the natural LP relaxation of $k$-median vanishes if we allow the integral solution to open $k+1$ facilities. This suggests that our reduction may bring in new avenues for approximating $k$-median. In particular, we find the following open problem interesting: given a $k$-median instance $\mathcal{I}$, what is the maximum ratio between the cost of the optimum integral solution of $\mathcal{I}$ with $k+1$ open facilities, and the LP value (with $k$ open facilities)?

To complement the first component, we give the aforementioned pseudo-approximation algorithm $\mathcal{A}$ with $\alpha=1+\sqrt{3}+\epsilon$. Prior to our work, it was not even known whether opening $k+o(k)$ facilities would help improve the approximation ratio; all known pseudo-approximation algorithms require $k+\Omega(k)$ open facilities. In contrast, our algorithm only opens $k+O(1/\epsilon)$ facilities. The algorithm $\mathcal{A}$ contains 2 steps. We obtain a bi-point solution for $k$-median using the algorithm of . We lose a factor of $2$ in this step. Then, we convert the bi-point solution into an integral solution with $k+O(1/\epsilon)$ open facilities, losing another factor of $\frac{1+\sqrt{3}+\epsilon}{2}$ in the approximation ratio. We remark that if we had insisted on opening $k$ facilities, then a factor of $2$ has to be lost in the last step as the instance achieving an integrality gap of $2$ has a bi-point solution.

Theorem 1 does not give a better upper bound on the integrality gap of the natural LP due to the following reason: instead of running the pseudo-approximation algorithm $\mathcal{A}$ on the input instance $\mathcal{I}$, we run it on a residual instance $\mathcal{I}^{\prime}$ obtained from $\mathcal{I}$ by removing a subset of facilities that the optimal solution does not open. The way we obtain $\mathcal{I}^{\prime}$ is to guess $O(1/\epsilon^{2})$ “events” and let $\mathcal{I}^{\prime}$ be the instance conditioned on these events. Due to this nature, our algorithm can be converted to a rounding algorithm based on solving an $O(1/\epsilon^{2})$-level LP in the Sherali-Adams hierarchy. Instead of guessing the $O(1/\epsilon^{2})$ events, we can now find these events explicitly by looking at the LP solution. Conditioning on these events, we obtain a fractional solution of the basic LP. By rounding this LP, we obtain a $1+\sqrt{3}+\epsilon$-approximate solution. Thus, our approach can be seen to give an $1+\sqrt{3}+\epsilon$-upper bound on the integrality gap of the $O(1/\epsilon^{2})$-level LP in the Sherali-Adams hierarchy. Our result was in fact first obtained by studying the power of the Sherali-Adams hierarchy for the $k$-median problem. However, as it can also be obtained using a combinatorial approach with less cumbersome notation, we have chosen to present that approach.

2 Preliminaries

Given a $k$-median instance $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$, a pseudo-solution to $\mathcal{I}$ is a set $\mathcal{S}\subseteq\mathcal{F}$. A pseudo-solution $\mathcal{S}$ satisfying $\left|\mathcal{S}\right|\leq k$ is a solution to $\mathcal{I}$; a pseudo-solution $\mathcal{S}$ with $\left|\mathcal{S}\right|\leq k+c$, for some number $c\geq 0$, is called a $c$-additive (pseudo-)solution. The cost of a pseudo-solution $\mathcal{S}$ to $\mathcal{I}$ is defined as $\mathsf{cost}_{\mathcal{I}}(\mathcal{S})=\sum_{j\in\mathcal{C}}d(j,\mathcal{S})$, where $d(j,\mathcal{S})$ denotes the distance from $j$ to its closest facility in $\mathcal{S}$. We let $\mathsf{OPT}_{\mathcal{I}}$ denote an optimal solution to $\mathcal{I}$, i.e., one of minimum cost, and we let $\mathsf{opt}_{\mathcal{I}}=\mathsf{cost}_{\mathcal{I}}(\mathsf{OPT}_{\mathcal{I}})$. To avoid confusion we will throughout the paper assume that the optimal solution is unique and that the concept of closest facility (or client) is also uniquely defined. This can be achieved either by slightly perturbing the metric or by simply breaking ties in an arbitrary but fixed way.

The standard linear programming relaxation for the $k$-median problem is formulated as follows.

Constraint (1a) says that we are allowed to open at most $k$ facilities, Constraint (1b) says that we must connect each client, and Constraint (1c) says that if we connect a client to a facility then that facility has to be opened.

As mentioned earlier, the above linear programming has an integrality gap of $2$, even when the underlying metric is a tree. The instance that gives the integrality gap of $2$ is depicted in Figure 1. It is a star with $k+1$ leaves. The center of the star is a facility and the leaves are both facilities and clients. Note that a pseudo-solution that opens all leaves, i.e., $k+1$ facilities, has cost whereas any solution that opens only $k$ facilities has cost $2$. The solution to the linear program obtained by a linear combination of the pseudo-solution that opens all leaves and the solution that only opens the center of the star has cost $1+1/k$ yielding the integrality gap of $2$ when $k$ tends to infinity. In general, a solution that is a linear combination of two pseudo-solutions is called a bi-point (fractional) solution. As this concept is important for our pseudo-approximation algorithm, we state its formal definition.

Let $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$ be a $k$-median instance. Let $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ be two pseudo-solutions to $\mathcal{I}$ such that $\left|\mathcal{S}_{1}\right|\leq k<\left|\mathcal{S}_{2}\right|$. Let $a\geq 0,b\geq 0$ be the real numbers such that $a+b=1$ and $a\left|\mathcal{S}_{1}\right|+b\left|\mathcal{S}_{2}\right|=k$. Then, the following fractional solution to $\mathcal{I}$, denoted by $a\mathcal{S}_{1}+b\mathcal{S}_{2}$, is called a bi-point (fractional) solution:

$y_{i}=a1_{i\in\mathcal{S}_{1}}+b1_{i\in\mathcal{S}_{2}}$;

$x_{i,j}=a1_{\mathsf{clst}(i,\mathcal{S}_{1},j)}+b1_{\mathsf{clst}(i,\mathcal{S}_{2},j)}$, where $\mathsf{clst}(i,\mathcal{S},j)$ denotes the event that $i$ is the closest facility in $\mathcal{S}$ to $j$.

It is easy to see that the cost of the fractional solution $a\mathcal{S}_{1}+b\mathcal{S}_{2}$ is exactly $a\mathsf{cost}_{\mathcal{I}}(\mathcal{S}_{1})+b\mathsf{cost}_{\mathcal{I}}(\mathcal{S}_{2})$. Jain and Vazirani gave a Lagrangian multiplier preserving $3$-approximation for UFL, which immediately yields an algorithm which produces a bi-point solution whose cost is at most $3$ times the optimum. Together with an algorithm which converts a bi-point solution to an integral solution at the cost of a factor $2$, gave a $6$-approximation for $k$-median. Later, the factor $3$ was improved by Jain et al. to $2$. We now formally state the result of .

Given a $k$-median instance $\mathcal{I}$, we can find in polynomial time a bi-point solution $a\mathcal{S}_{1}+b\mathcal{S}_{2}$ to $\mathcal{I}$ whose cost is at most 2 times the cost of an optimal solution to $\mathcal{I}$.

3 Overview of the Algorithm

The two components of our algorithm are formally stated in Theorem 4 and Theorem 5, whose proofs will be given in Sections 2 and 3, respectively. Together they immediately imply Theorem 1.

Let $\mathcal{A}$ be a $c$-additive $\alpha$-approximation algorithm for $k$-median, for some $\alpha>1$. Then, for every $\epsilon>0$ there is a $\alpha+\epsilon$-approximation algorithm $\mathcal{A}^{\prime}$ for $k$-median whose running time is $O\left(n^{O(c/\epsilon)}\right)$ times the running time of $\mathcal{A}$.

There exists a polynomial time algorithm which, given a $k$-median instance $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$ and $\epsilon>0$, produces an $O(1/\epsilon)$-additive $1+\sqrt{3}+\epsilon$-approximate solution to $\mathcal{I}$.

We now provide more details about the proof of the two theorems. At first glance, it seems that the transformation from a pseudo-approximation to a real approximation stated in Theorem 4 is impossible, since there are cases where allowing $k+1$ open facilities would give much smaller cost than only allowing $k$ open facilities. However, we show that we can pre-process the input instance so as to avoid these problematic instances. Roughly speaking, we say that a facility $i$ is dense if the clients in a small ball around $i$ contribute a lot to the cost of the optimum solution $\mathsf{OPT}$ (see Definition 6). We guess the $O(1/\epsilon)$ densest facilities and their respective nearest open facilities in $\mathsf{OPT}$. Then for each such dense facility $i$ whose nearest open facility in $\mathsf{OPT}$ is $i^{\prime}$, we remove all facilities that are closer to $i$ than $i^{\prime}$ (including the dense facility $i$). Then we get a residual instance in which the gap between the costs of opening $k+O(1)$ and $k$ facilities is small. The pseudo-approximation algorithm is then applied to this residual instance.

For example, consider the integrality gap instance depicted in Figure 1 and let $\mathsf{OPT}$ be the optimal solution that opens the center and $k-1$ leaves. Then the two leaves that were not opened contribute a large fraction of the total cost (each contributes $\mathsf{opt}/2$ to be precise) and the two corresponding facilities are dense. By removing these dense facilities in a preprocessing step, the gap between the costs of opening $k+O(1)$ facilities and $k$ facilities for the residual instance becomes small (actually in this example).

Regarding the proof of Theorem 5, we first use Theorem 3 to obtain a bi-point solution for $k$-median whose cost is at most twice the optimum cost. Jain and Vazirani showed how to convert a bi-point solution to an integral solution, losing a multiplicative factor of $2$ in the approximation. As we previously mentioned, this factor of $2$ is tight, as the fractional solution for the gap instance in Figure 1 is a bi-point solution. Thus, this approach can only yield a $4$-approximation.

This is where the $c$-additive pseudo-approximation is used and again the integrality gap instance depicted in Figure 1 inspired our approach. Recall that if we open the $k+1$ leaves of that instance, then we get a solution of cost . In other words, by opening $1$ additional facility, we can do better than the fractional solution. One may argue that this trick is too weak to handle more sophisticated cases and try to enhance the gap instance. A natural way to enhance it is to make many separate copies of the instance to obtain several “stars”. One might expect that the fractional cost in each copy is 1, the integral cost in each copy is 2 and opening $1$ more facility can only improve the integral solution of one copy and thus does not improve the overall ratio by too much. However, the integral solution can do much better since one cannot restrict the integral solution to open $k$ facilities in each star. As an example, consider the case where we have $2$ copies. The integral solution can open $k-1$ facilities in the first star, and $k+1$ facility in the second star. Then, the cost of this solution is $3$, as opposed to $4$ achieved by opening $k$ facilities in each star. The gap is already reduced to $1.5$, without opening additional facilities. Thus, this simple way to enhance the instance failed.

Our pseudo-approximation algorithm is based on this intuition. From the bi-point solution $a\mathcal{F}_{1}+b\mathcal{F}_{2}$, we obtain copies of “stars” (similar to the integrality gap instance). Then for each star we (basically) open either its center with probability $a$ or all its leaves with probability $b$. Note that since either the center or all leaves of a star is open we have that a client always has a “close” facility opened. With this intuition we prove in Section 3 that the expected cost of the obtained pseudo-solution is at most $\frac{1+\sqrt{3}+\epsilon}{2}$ times the cost of the bi-fractional solution if we open $O(1/\epsilon)$ additional facilities. The $O(1/\epsilon)$ additional facilities (and the case distinction in Section 3) comes from the difficulty of handling stars of different sizes. If all stars are of the same size the pseudo-approximation algorithm becomes easier (run the algorithm in Section 3.2 with one group of stars) and one obtains a $\frac{1+\sqrt{3}}{2}$-approximate solution that opens at most $k+3$ facilities.

Obtain solutions from additive pseudo-solutions

In this section, we prove Theorem 4. As we mentioned earlier, there are instances where pseudo-solutions opening $k+1$ facilities may have much smaller cost than solutions opening $k$ facilities. A key concept to overcome this issue is the notion of sparse instances:

For $A>0$, an instance $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$ is $A$-sparse if for each facility $i\in\mathcal{F}$,

where $\xi:=1/3$. We shall also say that a facility $i$ is $A$-dense if it violates (2).

Recall that $d(i,\mathsf{OPT}_{\mathcal{I}})$ is the distance from $i$ to its nearest facility in $\mathsf{OPT}_{\mathcal{I}}$.

The idea of the above definition is to avoid instances where we can significantly reduce the cost by opening $O(1)$ additional facilities. Consider the gap instance $\mathcal{I}$ in Figure 1 and suppose $\mathsf{OPT}_{\mathcal{I}}$ opens the center and the first $k-1$ leaf-facilities. Then $\mathcal{I}$ is not $A$-sparse for $A<\mathsf{opt}_{\mathcal{I}}/2$ since the last two leaf-facilities are $A$-dense.

The usefulness of the definition is twofold. On the one hand, we show that we can concentrate on very sparse instances without loss of generality. On the other hand, we show that any $c$-additive pseudo-solution to a sparse instance can be turned into a solution that opens $k$ facilities by only increasing the cost slightly. The intuition behind the result that we can only concentrate on sparse instances is the following. Consider an instance $\mathcal{I}$ that is not $\mathsf{opt}_{\mathcal{I}}/t$-sparse for some constant $t$. If we consider a facility $i$ that is $\mathsf{opt}_{\mathcal{I}}/t$-dense then the connection cost of the clients contained in $\mathsf{CBall}(i,\xi d(i,\mathsf{OPT}_{\mathcal{I}}))$ in the optimal solution $\mathsf{OPT}_{\mathcal{I}}$ is at least $(1-\xi)d(i,\mathsf{OPT}_{\mathcal{I}})|\mathsf{CBall}(i,\xi d(i,\mathsf{OPT}_{\mathcal{I}}))|>\mathsf{opt}_{\mathcal{I}}/t$. So, there can essentially (assuming disjointedness of the balls of clients) only be a constant $t$ number of facilities that violate the sparsity condition. We can guess this set of dense facilities, as well as their nearest facility in $\mathsf{OPT}_{\mathcal{I}}$ in time $n^{O(t)}$.

This is the intuition of Algorithm 1 (that tries to guess and remove $\mathsf{opt}/t$-dense facilities) and the proof of the following lemma which is given in Section 2.1.

Given a $k$-median instance $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$ and a positive integer $t$, Algorithm 1 outputs in time $n^{O(t)}$ many $k$-median instances obtained by removing facilities from $\mathcal{I}$ so that at least one, say $\mathcal{I}^{\prime}=(k,\mathcal{F}^{\prime}\subseteq\mathcal{F},\mathcal{C},d)$, satisfies

the optimal solution $\mathsf{OPT}_{\mathcal{I}}$ to $\mathcal{I}$ is also an optimal solution to $\mathcal{I}^{\prime}$; and

$\mathcal{I}^{\prime}$ is $\mathsf{opt}_{\mathcal{I}}/t$-sparse.

Note that $\mathcal{I}^{\prime}$ is obtained by removing facilities from $\mathcal{I}$. Therefore any solution to $\mathcal{I}^{\prime}$ defines a solution to $\mathcal{I}$ of the same cost and we can thus restrict our attention to sparse instances. The next lemma shows the advantage of considering such instances. Assume we now have a $c$-additive solution $\mathcal{T}$ to a sparse instance $\mathcal{I}$. Algorithm 2 tries first in Lines 2-3 to identify facilities in $\mathcal{T}$ whose removal does not increase the cost by too much. If the removal results in a set of at most $k$ facilities, we have obtained a “good” solution returned at Step 4 of the algorithm. Otherwise, as we prove in Section 2.2 using sparsity, more than $k-t$ of the facilities of the solution $\mathcal{T}$ are very close to facilities in $\mathsf{OPT}_{\mathcal{I}}$. Algorithm 2 therefore tries to guess these facilities (the set $\mathcal{D}$) and the remaining facilities of $\mathsf{OPT}_{\mathcal{I}}$ (the set $\mathcal{V}$). The obtained bounds are given in the following lemma.

Given an $A$-sparse instance $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$, a $c$-additive pseudo-solution $\mathcal{T}$, $\delta\in(0,1/8)$, and an integer $t\geq 2c/(\delta\xi)$, Algorithm 2 finds in time $n^{O(t)}$ a set $\mathcal{S}\subseteq\mathcal{F}$ such that:

$\mathcal{S}$ is a solution to $\mathcal{I}$, i.e, $|\mathcal{S}|\leq k$; and

$\mathsf{cost}_{\mathcal{I}}(\mathcal{S})\leq\max\left\{\mathsf{cost}_{\mathcal{I}}(\mathcal{T})+cB,\frac{1+3\delta}{1-3\delta}\cdot\mathsf{opt}_{\mathcal{I}}\right\}$, where $B:=2\cdot\frac{A+\mathsf{cost}_{\mathcal{I}}(\mathcal{T})/t}{\xi\delta}$.

Before giving the proofs of Lemmas 7 and 8 let us see how they imply the main result of this section.

Select the largest $\delta\in(0,1/8)$ such that $(1+3\delta)/(1-3\delta)\leq\alpha$ and $t:=\frac{4}{\epsilon}\cdot\frac{\alpha c}{\xi\cdot\delta}=O(c/\epsilon)$. Given a $k$-median instance $\mathcal{I}$, use Algorithm 1 to obtain a set of $k$-median instances such that at least one of these instances, say $\mathcal{I}^{\prime}$, satisfies the properties of Lemma 7. In particular, $\mathcal{I}^{\prime}$ is $\mathsf{opt}_{\mathcal{I}}/t$-sparse. Now use algorithm $\mathcal{A}$ to obtain $c$-additive pseudo-solutions to each of these instances. Note that when we apply $\mathcal{A}$ to $\mathcal{I}^{\prime}$, we obtain a solution $\mathcal{T}$ such that $\mathsf{cost}_{\mathcal{I}}(\mathcal{T})=\mathsf{cost}_{\mathcal{I}^{\prime}}(\mathcal{T})\leq\alpha\cdot\mathsf{opt}_{\mathcal{I}^{\prime}}=\alpha\cdot\mathsf{opt}_{\mathcal{I}}$. Finally, use Algorithm 2 (with the same $t$ and $\delta$ selected as above) to transform the pseudo-solutions into real solutions and return the solution to $\mathcal{I}$ of minimum cost. The cost of the returned solution is at most the cost of $\mathcal{S}$ where $\mathcal{S}$ is the solution obtained by transforming $\mathcal{T}$. By Lemmas 7 and 8, we have that $\mathsf{cost}_{\mathcal{I}}(S)=\mathsf{cost}_{\mathcal{I}^{\prime}}(S)$ is at most

which in turn, by the selection of $\delta,\xi$, and $t$, is at most $\alpha\mathsf{opt}_{\mathcal{I}}+c\cdot\frac{4\alpha\mathsf{opt}_{\mathcal{I}}}{t\xi\delta}\leq(\alpha+\epsilon)\mathsf{opt}_{\mathcal{I}}$.

We conclude the proof of Theorem 4 by observing that the runtime of the algorithm is $n^{O(t)}=n^{O(c/\epsilon)}$ times the runtime of $\mathcal{A}$.

1 Proof of Lemma 7: obtaining a sparse instance

$i_{b}\in\mathcal{F}\setminus\bigcup_{z=1}^{b-1}\mathsf{FBall}(i_{z},d(i_{z},i^{\prime}_{z}))$ is an $\mathsf{opt}_{\mathcal{I}}/t$-dense facility; and

$i^{\prime}_{b}$ is the closest facility to $i_{b}$ in $\mathsf{OPT}_{\mathcal{I}}$.

which implies that the balls do not overlap.

2 Proof of Lemma 8: obtain solution to sparse instance from pseudo-solution

We start by analyzing the running time of Algorithm 2. Clearly the while loop can run at most $c$ iterations (a constant). The number of different pairs $(\mathcal{D},\mathcal{V})$ in the for loop is at most

We proceed by proving that $\mathcal{S}$ satisfies (8b) of Lemma 8. Suppose first that the algorithm returns at Line 4. By the condition of the while loop from Line 2 to 3, we increase $\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})$ by at most $B$ each time we remove an element from $\mathcal{T}^{\prime}$. We remove at most $c$ elements and thus we increase the total cost by at most $cB$. It follows that (8b) is immediately satisfied in this case.

From now on suppose instead that we reached Line 5 of Algorithm 2 and thus $\left|\mathcal{T}^{\prime}\right|>k$. We shall exhibit sets $\mathcal{D}_{0}$ and $\mathcal{V}_{0}$ such that $|\mathcal{D}_{0}|+|\mathcal{V}_{0}|=k$, $|\mathcal{V}_{0}|<t$ and $\mathsf{cost}(\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}})\leq\frac{1+3\delta}{1-3\delta}\mathsf{opt}_{\mathcal{I}}$. As Algorithm 2 selects $\mathcal{D}_{0}$ and $\mathcal{V}_{0}$ in one iteration and it returns the minimum cost solution, this concludes the proof of Lemma 8. In order to define the sets $\mathcal{D}_{0}$ and $\mathcal{V}_{0}$ it shall be convenient to use the following definitions.

The sets $\mathcal{D}_{0}$ and $\mathcal{V}_{0}$ are now defined as follows. Set $\mathcal{D}_{0}$ contain all facilities in $i\in\mathcal{T}^{\prime}$ that are determined. If we let $f_{i}^{*}$ for $i\in\mathcal{D}_{0}$ be the facility in $\mathsf{OPT}_{\mathcal{I}}$ that is closest to $i$, then set $\mathcal{V}_{0}:=\mathsf{OPT}_{\mathcal{I}}\setminus\{f_{i}^{*}:i\in\mathcal{D}_{0}\}$. The intuition of $\mathcal{D}_{0}$ and $\mathcal{V}_{0}$ is that the solution $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$ is very close to $\mathsf{OPT}_{\mathcal{I}}$: the only difference is the selection of $f_{i}$ at Line 6 of Algorithm 2 instead of $f_{i}^{*}$. Since each $i\in\mathcal{D}_{0}$ is determined, selecting $f_{i}$ greedily using a “locally” optimal strategy gives a good solution.

We first show that sets $\mathcal{D}_{0}$ and $\mathcal{V}_{0}$ are indeed selected by Algorithm 2 and then we conclude the proof of the lemma by bounding the cost of $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$.

$|\mathcal{D}_{0}|+|\mathcal{V}_{0}|=k$ and $|\mathcal{V}_{0}|<t$.

We start by proving that $|\mathcal{D}_{0}|+|\mathcal{V}_{0}|=k$. Recall that $\mathcal{V}_{0}=\mathsf{OPT}_{\mathcal{I}}\setminus\{f_{i}^{*}:i\in\mathcal{D}_{0}\}$. It is not hard to see that $f^{*}_{i}\neq f^{*}_{i^{\prime}}$ for two distinct facilities in $\mathcal{D}_{0}$. This is indeed true since $d(i,i^{\prime})\geq\max(L_{i},L_{i^{\prime}}),d(i,f^{*}_{i})\leq\delta L_{i},d(i^{\prime},f^{*}_{i^{\prime}})\leq\delta L_{i^{\prime}}$ and $\delta\leq 1/8$. Thus, $f^{*}(\mathcal{D}_{0}):=\left\{f^{*}_{i}:i\in\mathcal{D}_{0}\right\}$ has size $\left|\mathcal{D}_{0}\right|$, which in turn implies that (to simplify calculations we assume w.l.o.g. that $|\mathsf{OPT}_{\mathcal{I}}|=k$)

We proceed by proving $|\mathcal{V}_{0}|<t$. Note that the sets of determined and undetermined facilities partition $\mathcal{T}^{\prime}$. Therefore, if we let $\mathcal{U}_{0}$ be the set of undetermined facilities, we have that $|\mathcal{D}_{0}|=|\mathcal{T}^{\prime}|-|\mathcal{U}_{0}|.$ Combining this with the above expression for $|\mathcal{V}_{0}|$ gives us

We complete the proof of the claim by showing that $|\mathcal{U}_{0}|<t$.

By the assumption that we reached Line 5 of Algorithm 2, we have $\left|\mathcal{T}^{\prime}\right|>k$ and $\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime}\setminus\left\{i\right\})>\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})+B$ for every $i\in\mathcal{T}^{\prime}$. Assume towards contradiction that $\left|\mathcal{U}_{0}\right|\geq t$. For every $i\in\mathcal{T}^{\prime}$, let $\mathcal{C}_{i}$ be the set of clients in $\mathcal{C}$ connected to $i$ in the solution $\mathcal{T}^{\prime}$ and $C_{i}$ be the total connection cost of these clients. Thus, $\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})=\sum_{i\in\mathcal{T}^{\prime}}C_{i}$. Take the facility $i\in\mathcal{U}_{0}$ with the minimum $C_{i}$. Then, we have $C_{i}\leq\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})/t$. Let $i^{\prime}$ be the nearest neighbor of $i$ in $\mathcal{T}^{\prime}$; thus $d(i,i^{\prime})=L_{i}$.

We shall remove the facility $i$ from $\mathcal{T}^{\prime}$ and connect the clients in $\mathcal{C}_{i}$ to $i^{\prime}$. In order to consider incremental connection cost incurred by the operation, we divide $\mathcal{C}_{i}$ into two parts.

Then, as each client in $\mathcal{C}_{i}\cap\mathsf{CBall}(i,\delta\xi L_{i})$ has distance at most $(1+\delta\xi)L_{i}$ to $i^{\prime}$ (by triangle inequalities), connecting all clients in $\mathcal{C}_{i}\cap\mathsf{CBall}(i,\delta\xi L_{i})$ to $i^{\prime}$ can cost at most $A/(\delta\xi)$.

Consider any client $j$ in this set. Since $d(j,i^{\prime})\leq d(j,i)+L_{i}$ and $d(j,i)\geq\delta\xi L_{i}$, we have $\frac{d(j,i^{\prime})-d(j,i)}{d(j,i)}\leq\frac{L_{i}}{\delta\xi L_{i}}=1/(\delta\xi)$. Hence, the connection cost of a single client is increased by at most a factor $1/(\delta\xi)$. Therefore, the total connection cost increases by at most $C_{i}/(\delta\xi)$, which by the selection of $i$ is at most $\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})/(\delta\xi t).$

Summing up the two quantities, removing $i$ from $\mathcal{T}^{\prime}$ can only increase the connection cost by at most $\frac{A+\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})/t}{\delta\xi}$. As the while loop of Algorithm 2 ran for less than $c$ iterations, $\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})<\mathsf{cost}_{\mathcal{I}}(\mathcal{T})+cB$. Therefore, $\frac{A+\mathsf{cost}_{\mathcal{I}}(\mathcal{T}^{\prime})/t}{\delta\xi}<\frac{A+(\mathsf{cost}_{\mathcal{I}}(\mathcal{T})+cB)/t}{\delta\xi}$ which since $t\geq 2c/(\delta\xi)$ is at most $\frac{A+\mathsf{cost}_{\mathcal{I}}(\mathcal{T})/t}{\delta\xi}+B/2=B$ leading to a contradiction. Hence, $|\mathcal{U}_{0}|<t$ which concludes the proof of the claim. $\square$

Having proved that the instance $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$ is selected by Algorithm 2, we conclude the proof of Lemma 8 by bounding the cost of $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$.

Recall that, for every $i\in\mathcal{D}_{0}$, Algorithm 2 opens one facility $f_{i}$ in the ball $\mathsf{FBall}(i,\delta L_{i})$. We know we can do this so that the connection cost of $\mathcal{C}$ is $\mathsf{opt}_{\mathcal{I}}$. We show that we can approximate this instance within a factor of $1+O(\delta)$. Roughly speaking, if a client is far away from any of these balls, then it does not care which facilities to open inside the balls, up to a factor $1+O(\delta)$. If a client is close to one of these balls, say $\mathsf{FBall}(i,\delta L_{i})$, then we put the client into the “care-set” of $i$. For each $i$, we open a facility in the ball that is best for its care-set.

To be more specific, let the care-set of $i$ be $\mathsf{CBall}(i,L_{i}/3)$ for any $i\in\mathcal{D}_{0}$. Clearly, the balls $\mathsf{CBall}(i,L_{i}/3),i\in\mathcal{D}_{0}$ are disjoint. As stated in Line 6 of Algorithm 2, we open a facility $f_{i}$ in $\mathsf{FBall}(i,\delta L_{i})$ that minimizes

$\mathsf{cost}_{\mathcal{I}}(\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}})\leq\frac{1+3\delta}{1-3\delta}\mathsf{opt}_{\mathcal{I}}$.

We compare $\mathsf{OPT}_{\mathcal{I}}$ and $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$. Consider a client $j\in\mathsf{CBall}(i,L_{i}/3)$ for some $i\in\mathcal{D}_{0}$. The distance from $j$ to any facility in $\mathsf{FBall}(i,\delta L_{i})$ is at most $(1/3+\delta)L_{i}$. For any distinct facility $i^{\prime}\in\mathcal{D}_{0}$, the distance from $j$ to any facility in $\mathsf{FBall}(i^{\prime},\delta L_{i^{\prime}})$ is at least $d(i,i^{\prime})-L_{i}/3-\delta L_{i^{\prime}}\geq d(i,i^{\prime})-d(i,i^{\prime})/3-\delta d(i,i^{\prime})=(2/3-\delta)d(i,i^{\prime})\geq(2/3-\delta)L_{i}$. For $\delta\leq 1/8$, $1/3+\delta<2/3-\delta$. Thus, $j$ is either connected to $f^{*}_{i}$ or some facility in $\mathcal{V}_{0}$ in the solution $\mathsf{OPT}_{\mathcal{I}}$. Noticing that we are selecting the best $f_{i}$ for every $i\in\mathcal{D}_{0}$, the total connection cost of $\bigcup_{i\in\mathcal{D}_{0}}\mathsf{CBall}(i,L_{i}/3)$ in the solution $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$ is at most that in $\mathsf{OPT}_{\mathcal{I}}$.

Now, consider a client $j$ that is not in $\bigcup_{i\in\mathcal{D}_{0}}\mathsf{CBall}(i,L_{i}/3)$. If it is connected to some facility in $\mathcal{V}_{0}$ in the solution $\mathsf{OPT}_{\mathcal{I}}$, then the connection cost of $j$ in the solution $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$ can not be larger, since $\mathcal{V}_{0}\subseteq\mathcal{S}$. Assume $j$ is connected to $f^{*}_{i}\in\mathsf{CBall}(i,L_{i}/3)$ for some $i\in\mathcal{D}_{0}$. We compare $d(j,f^{*}_{i})$ to $d(j,f_{i})$:

Thus, $\mathcal{S}_{\mathcal{D}_{0},\mathcal{V}_{0}}$ has connection cost at most $\frac{1+3\delta}{1-3\delta}\mathsf{opt}_{\mathcal{I}}$. $\square$

An O​(1/ϵ)𝑂1italic-ϵO(1/\epsilon)-additive 1+3+ϵ13italic-ϵ1+\sqrt{3}+\epsilon approximation for k𝑘k-median

13italic-ϵ1+\sqrt{3}+\epsilon approximation for $k$-median This section is dedicated to prove Theorem 5. Given a $k$-median instance $\mathcal{I}=(k,\mathcal{F},\mathcal{C},d)$, we first use Theorem 3 to obtain a bi-point solution $a\mathcal{S}_{1}+b\mathcal{S}_{2}$ whose cost is at most $2$ times the optimum cost of $\mathcal{I}$. Then it suffices to convert $a\mathcal{S}_{1}+b\mathcal{S}_{2}$ into an $O(1/\epsilon)$-additive solution, whose cost is at most $\frac{1+\sqrt{3}+\epsilon}{2}$ times that of $a\mathcal{S}_{1}+b\mathcal{S}_{2}$.

By the definition of bi-point solutions, we have $a+b=1,|\mathcal{F}_{1}|\leq k<|\mathcal{F}_{2}|$ and $a|\mathcal{F}_{1}|+b|\mathcal{F}_{2}|=k$. It shall be convenient to think of $a\mathcal{F}_{1}+b\mathcal{F}_{2}$ as a bipartite graph (see Figure 3) with vertex sets $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ and an edge for each client $j\in\mathcal{C}$ that is incident to its closest facilities in $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ denoted by $i_{1}(j)$ and $i_{2}(j)$, respectively. Moreover, let $d_{1}(j):=d(j,i_{1}(j))$ and $d_{2}(j):=d(j,i_{2}(j))$. Then, the (fractional) connection cost of $j$ in the bi-point solution is $ad_{1}(j)+bd_{2}(j)$. Similarly, if we let $d_{1}:=\mathsf{cost}(\mathcal{F}_{1})=\sum_{j\in\mathcal{C}}d_{1}(j)$ and $d_{2}:=\mathsf{cost}(\mathcal{F}_{2})=\sum_{j\in\mathcal{C}}d_{2}(j)$ then the bi-point solution has cost $ad_{1}+bd_{2}$.

We shall prove Theorem 5 by exhibiting different algorithms based on the value of $a$. Specifically, we shall distinguish between the cases when $a$ is in $\left(0,\frac{\sqrt{3}-1}{4}\right],\left(\frac{\sqrt{3}-1}{4},\frac{2}{1+\sqrt{3}}\right],$ and $\left(\frac{2}{1+\sqrt{3}},1\right]$. The simplest case is when $a\in\left(\frac{2}{1+\sqrt{3}},1\right]$: the solution where we open all facilities in $\mathcal{F}_{1}$ is then a $\frac{d_{1}}{ad_{1}+bd_{2}}\leq 1/a=(1+\sqrt{3})/2$ approximation.

For the two remaining cases, we will use the concept of stars. For each facility $i\in\mathcal{F}_{2}$ define $\pi(i)$ to be the facility in $\mathcal{F}_{1}$ that is closest to $i$. For a facility $i\in\mathcal{F}_{1}$ , let $S_{i}=\{i^{\prime}\in\mathcal{F}_{2}:\pi(i^{\prime})=i\}$. We think of $S_{i}$ as a star with center $i$ and leaves $S_{i}$. Note that by the definition of stars, we have that any client $j$ with $i_{2}(j)\in S_{i}$ has $d(i_{2}(j),i)\leq d(i_{2}(j),i_{1}(j))=d_{2}(j)+d_{1}(j)$ and therefore $d(j,i)\leq d(j,i_{2}(j))+d(i_{2}(j),i)\leq 2d_{2}+d_{1}$. Our algorithms will ensure that there is an open facility “close” to every client by always opening $i$ if not all facilities in $S_{i}$ are opened. The strategy for either opening the center of a star or its leaves (or sometimes both) depends on the value of $a$. We start in Section 3.1 by explaining the simpler case when $a\in\left(0,\frac{\sqrt{3}-1}{4}\right]$ and then complete the proof of Theorem 5 by considering the final case in Section 3.2.

The idea behind our algorithm is that when $a$ is small then we can open most facilities in $\mathcal{F}_{2}$. We shall do so by starting with the trivial solution $\mathcal{F}_{1}$ that we will improve by almost greedily selecting stars and open all their leaves while closing their centers.

As we will maintain the property that $i$ is open if not all facilities in $S_{i}$ are open, we have that the connection cost of a client $j$ is $d_{2}(j)$ if $i_{2}(j)$ is open and at most $d_{1}(j)+2d_{2}(j)$ otherwise. Consider the trivial solution where we open all facilities in $\mathcal{F}_{1}$. Then the total connection cost is upper-bounded by $\sum_{j}(d_{1}(j)+2d_{2}(j))$. If we open the facilities in $S_{i}$ instead of $i$ this will save us the cost $\sum_{j\in\delta(S_{i})}(d_{1}(j)+d_{2}(j))$, where $\delta(S_{i})$ denotes the clients that are incident to the facilities in $S_{i}$. This motivates the following linear program that maximizes the cost we will save compared to the trivial solution:

Intuitively, $x_{i}$ takes value $1$ if we open all the facilities in $S_{i}$ and if we open $i$. If $x_{i}=1$, we need to open $\left|S_{i}\right|-1$ more facilities (i.e, close $i$ and open all facilities in $S_{i}$). Thus, the constraint says that we can only open $k$ facilities. Note that this is a Knapsack LP and hence it is easy to see that an optimal solution has at most one fractional variable. Furthermore, $x_{i}=b$ is a feasible solution since $b\left|\mathcal{F}_{2}\right|-b\left|\mathcal{F}_{1}\right|=k-\left|\mathcal{F}_{1}\right|$. Therefore, the optimal solution to the LP has value at least $b(d_{1}+d_{2})$.

Consider an optimal solution to the Knapsack LP with at most 1 fractional variable. Then, we open all the facilities in $S_{i}$ with $x_{i}=1$, all the facilities $i\in\mathcal{F}_{1}$ with $x_{i}=0$, and for the $i$ with fractional $x_{i}$ we open $i$ and $\left\lceil x_{i}|S_{i}|\right\rceil$ facilities in $S_{i}$ uniformly at random. (This step can easily be derandomized by greedily selecting the $\left\lceil x_{i}|S_{i}|\right\rceil$ facilities in $S_{i}$ that maximizes the reduced cost.)

Note that we opened the facilities so that the (expected) saved cost compared to the trivial solution is at least the value of the optimal solution to the linear program. Therefore, this gives us a solution of (expected) cost at most $2d_{2}+d_{1}-b(d_{2}+d_{1})=(1+a)d_{2}+ad_{1}$. Also, the solution opens at most $k+2$ facilities, where the additive term 2 comes from the star $S_{i}$ with fractional $x_{i}$ value.

Since we can assume that $d_{2}\leq d_{1}$ (otherwise we can simply open all facilities in $\mathcal{F}_{1}$), the algorithm has an approximation guarantee of

which is at most $\frac{1+\sqrt{3}}{2}$ if $a\leq\frac{\sqrt{3}-1}{4}$.

2 Algorithm for a∈(3−14,21+3]𝑎314213a\in\left(\frac{\sqrt{3}-1}{4},\frac{2}{1+\sqrt{3}}\right]

13a\in\left(\frac{\sqrt{3}-1}{4},\frac{2}{1+\sqrt{3}}\right] In this subsection, we give the algorithm for the most complex case. To simplify the arguments, we give a randomized algorithm that can easily be derandomized using the standard method of conditional probabilities. The idea is that we wish to describe a randomized rounding that opens a facility in $\mathcal{F}_{1}$ with probability $\approx a$ and a facility in $\mathcal{F}_{2}$ with probability $\approx b$ and at the same time ensuring that there always is an open facility “close” to a client by maintaining the property: if $i$ is not open then all facilities in $S_{i}$ are open for all stars.

We now describe such a randomized rounding that takes a parameter $\eta>0$ that balances the achieved approximation guarantee with the amount of additional facilities we open: the achieved approximation ratio is $(1+\eta)\frac{1+\sqrt{3}}{2}$ while we open at most $k+O(1/\eta)$ facilities. It shall be convenient to distinguish between large and small stars. We say that a star $S_{i}$ is large if $|S_{i}|\geq 2/(ab\eta)$ and small otherwise. Moreover, we partition the small stars into $\left\lceil 2/(ab\eta)\right\rceil$ groups according to their sizes:

The randomized algorithm can now be described as follows:

We start by showing that the algorithm does not open too many facilities; we then continue by bounding the expected cost of the obtained solution.

The algorithm opens at most $k+3\left\lceil 2/(ab\eta)\right\rceil$ facilities.

Recall that we have that $a\left|\mathcal{F}_{1}\right|+b\left|\mathcal{F}_{2}\right|=k$ and therefore

First, consider a large star $i\in\mathcal{F}_{1}$, i.e., $a|S_{i}|\geq 1/(b\eta)\geq 1/\eta$. For such a star, the algorithm opens $1+\lfloor b(|S_{i}|-1)\rfloor\leq 1+b(|S_{i}|-1)=a+b|S_{i}|$ facilities, which is the contribution of star $i$ to (3).

Second, consider a group $\mathcal{U}_{h}$ of small stars and let $m:=|\mathcal{U}_{h}|$. When considering this group, the algorithm opens $\lceil am\rceil+1\leq am+2$ facilities in $\mathcal{F}_{1}$, and at most

facilities in $\mathcal{F}_{2}$. Thus, the total number of facilities open from the group $\mathcal{U}_{h}$ of small stars is at most $m(a+bh)+3$. As $m$ is the size of $\mathcal{U}_{h}$ and $a+bh$ is the contribution of each star in $\mathcal{U}_{h}$ to (3), the statement follows from that we have at most $\left\lceil 2/(ab\eta)\right\rceil$ groups. $\square$

We proceed by bounding the expected cost of the obtained solution. The intuition behind the following claim is that we have designed a randomized algorithm that opens a facility in $\mathcal{F}_{2}$ with probability $\approx b$ and a facility in $\mathcal{F}_{1}$ with probability $\approx a$. Therefore, if we connect a client $j$ to $i_{2}(j)$ with connection cost $d_{2}(j)$ if that facility is open, to $i_{1}(j)$ with connection cost $d_{1}(j)$ if that facility but not $i_{2}(j)$ is open, and to the center $i$ of the star $S_{i}:i_{2}(j)\in S_{i}$ with connection cost at most $2d_{2}(j)+d_{1}(j)$ if neither $i_{1}(j)$ or $i_{2}(j)$ are opened (recall that $i$ is open if not all facilities in $S_{i}$ are open), then the expected connection cost of client $j$ is at most