The $k$-median problem is defined as follows: Given a set $C$ of clients and a set $L$ of facility locations defined over a distance metric $d$. Open a set $F$ of $k$ facility in $L$ such that the total cost of assigning the clients to their closest facilities is minimized, i.e.,

$$minimize \quad \Phi(F,C) \equiv \sum_{j = 1}^{|C|} \, \min_{f \in F} \big\{ d(j,f) \big\}$$

Suppose the optimal cost of the instance is denoted by $OPT$.

Is there any bi-criteria approximation algorithm for the problem that opens $f(k,\epsilon)$ facilities and gives $(1+\epsilon)$-approximation with respect to $OPT$ for any computable function $f$? The running time of the algorithm is allowed to be $g(k,\epsilon) \cdot n^{O(1)}$ for any computable function $g$.

Note: I know that in the Euclidean space the problem does have such a type of algorithm. But I am particularly interested in general metric spaces.

  • $\begingroup$ Are you asking for a polynomial-time algorithm? $\endgroup$
    – Neal Young
    Commented Jun 15, 2021 at 2:15
  • $\begingroup$ @NealYoung That was an important point. I have edited the question. Thank You! $\endgroup$ Commented Jun 15, 2021 at 3:14
  • 1
    $\begingroup$ I though such a result should be known but I couldn't find it. A paper by Hsu and Telgarsky may be helpful to look at. arxiv.org/abs/1607.06203 $\endgroup$ Commented Jun 15, 2021 at 12:37

2 Answers 2


We improve Chandra's bound, as he conjectured was possible, giving an approximation algorithm that opens $f(k,\epsilon)=O(k\log (1/\epsilon))$ facilities to obtain assignment cost at most $1+\epsilon$ times the optimal with $k$ facilities.

Theorem 1. There is a polynomial-time algorithm that, given any metric $k$-medians instance, returns a solution that uses $O(k\log(1/\epsilon))$ facilities with assignment cost $1+O(\epsilon)$ times the optimum with $k$ facilities.

Proof. We use the same idea that Chandra does, but instead of using Lin and Vitter's filtering technique, we adapt the improved rounding scheme from K-medians, facility location, and the Chernoff-Wald bound.

Fix any optimal solution $(x, y)$ to the standard $k$-median linear-program relaxation: $$ \begin{align*} & & \min \textstyle \sum_{j\in C}\sum_{f\in L} d(j, f) x_{jf} \\ & (\forall j\in C) & \textstyle \sum_{f\in L} x_{jf} = 1, \\ & & \textstyle \sum_{f\in L} y_f = k, \\ & (\forall j\in C, f\in L) & 0 \le x_{jf} \le y_f. \end{align*} $$ Let $\alpha_j = \sum_{f\in L} d(j, f) x_{jf}$ be the assignment cost incurred by $(x, y)$ for client $j$. Let OPT $= \sum_j \alpha_j$ be the total assignment cost. The LP is a relaxation of the actual instance, so the true optimum is at least OPT.

The rounding scheme has two phases. In the first phase it generates a set $S\subseteq L$ of facilities and a partial assignment of clients to facilities in $S$, by sampling $h=\lceil k\ln(1/\epsilon)\rceil$ times as follows:

  1. for $t=1,2,\ldots, h$:
  2. $~~~~$ sample a random facility $f_t\in L$ from the distribution defined by $y/k$
  3. $~~~~$ for each unassigned client $j\in C$, with probability $x_{jf_t}/y_{f_t}$, assign $j$ to facility $f_t$
  4. let $A$ be the set of assigned clients

In each iteration, the chance of assigning a given unassigned client $j$ to a given facility $f$ is $\frac{y_f}{k} \frac{x_{jf}}{y_f} = \frac{x_{jf}}{k}$.

In each iteration, the probability of assigning a given unassigned client $j$ to some facility is $\sum_{f} \frac{x_{jf}}{k} = \frac 1 k$. So the chance that any given client is not in $A$ (not assigned during the first phase) is $p = (1-1/k)^h \le \exp(-h/k) \le \epsilon$.

For any given client $j$, conditioned on $j$ being in $A$ (assigned to some facility during the first phase), the expected cost of its assignment is $\sum_f x_{jf} d(j, f) = \alpha_j$. Thus the expected cost of the first phase is $\sum_j (1-p)\alpha_j = (1-p)$OPT.

In the second phase, (following Chandra's approach) use any existing $O(1)$-approximation algorithm to find an $O(1)$-approximate solution (w.r.t. the induced LP, and using here that the problem is metric) to the $k$-medians instance obtained from the given instance by removing all clients that were assigned in the first phase. This step opens at most $k$ facilities and (because the induced LP's solution costs at most $\sum_{j\not \in A} \alpha_j$) incurs assignment cost $O(\sum_{j\not\in A} \alpha_j)$. So by linearity of expectation the expected cost of this phase is $O(\sum_j \Pr[j\not\in A] \alpha_j) = O(\sum_j p \alpha_j) = O(p \,\text{OPT})$.

Thus, in total at most $k + 1 + k\ln(1/\epsilon)$ facilities are opened, and the expected assignment cost is at most $(1-p)\text{OPT} + O(p\,\text{OPT}) = (1+O(\epsilon))$OPT. $~~~\Box$

  • 2
    $\begingroup$ Nice. I was going to try the randomized algorithm/analysis but you were too fast :). One should also check and compare with Hsu-Telgarsky analysis who basically do greedy. I will look later today. $\endgroup$ Commented Jun 15, 2021 at 16:46
  • $\begingroup$ The paper of Makarychev, Makarychev, Ward essentially has this implicitly. Their main goal is k-means in high-dimensional Euclidean space and in fact they have to deal with the issue of centers being feasible in the ambient space. arxiv.org/abs/1507.04227. $\endgroup$ Commented Jun 15, 2021 at 17:07
  • $\begingroup$ @ChandraChekuri Just want to add something more. The centers being feasible in the ambient space do not cause a problem in the Euclidean space, since an $\alpha$-approximation for the discrete k-median gives an $\alpha(1+\epsilon)$-approximation in the continuous Euclidean space. The reduction follows from the weak-coreset construction of Feldman et al. :-) $\endgroup$ Commented Jun 15, 2021 at 17:52
  • $\begingroup$ This may generalize to the problem with outliers since it basically relies on having a constant factor approximation with respect to LP for an underlying problem. Perhaps there is a simple framework here that may work for a class of problems. $\endgroup$ Commented Jun 15, 2021 at 21:06
  • 1
    $\begingroup$ Thanks! Just one last thing. I think there is typo in the main theorem and the first paragraph. It should be $O( k \log(1/\epsilon))$. $\endgroup$ Commented Jun 16, 2021 at 14:00

Historically Lin and Vitter showed that one can obtain a $(2+\epsilon, k(1+1/\epsilon))$ bi-criteria approximation via a simple filtering trick with respect to the LP. This was before a constant factor approximation was shown via the LP. After that there seemed to be less interest in a bi-criteria PTAS even though it was explored extensively in geometric settings. Here is a sketch for $k$-median that seems to give a $(1+\epsilon)$-approximation using $O(k\log(1/\epsilon)/\epsilon)$ centers.

Consider solving the standard LP for $k$-median. Let $y_a$ be the amount of center opened at location $a$. For each point $v$ we can define $\alpha_v$ to be the distance paid by $v$ in the LP. Note that the total LP cost is $\sum_v \alpha_v$ which is a lower bound on the optimum integer cost. For each $v$ define $B_v$ to be a ball of radius $(1+\epsilon)\alpha_v$. Via Lin-Vitter style filtering idea, we can obtain a new LP solution that uses $O(k/\epsilon)$ centers with the property that for each $v$, there is a total fractional center of at least $1$ in $B_v$. We now set up a weighted Set Cover instance. We want to find centers such that every ball $B_v$ is hit by a center. We have a fractional solution with $O(k/\epsilon)$ centers. We can show that Greedy with $O(k \log (1/\delta)/\epsilon)$ centers will cover at least $(1-\delta)$ fraction of the balls. We can do this in the weighted sense as well where weight of $v$ is $\alpha_v$. So we run Greedy with $\delta = \epsilon$ and obtain a collection of $O(k \log (1/\epsilon)/\epsilon)$ centers. Let $H$ be the set of points $v$ such that $B_v$ is not hit by the chosen centers. We have $\sum_{v\in H} \alpha_v \le \epsilon \sum_v \alpha_v$. For these uncovered points we can use a constant factor (or even bicriteria) approximation for $k$-median via the LP. Thus the total cost will be $(1+O(\epsilon))\sum_v \alpha_v$ and the total number of centers used will be $O(k \log(1/\epsilon)/\epsilon)$.

I wonder if one can use only $O(k\log(1/\epsilon))$ centers. I think it may be possible by being more careful.

  • $\begingroup$ Chandra, very nice. BTW which result by Lin and Vitter do you have in mind? (I know about their paper "$\epsilon$-Approximations with Packing Constraint Violation", but that is for non-metric and gives a $(1+\epsilon, k(1+1/\epsilon)(1+\ln n))$-bicriteria approximation [Theorem 1]), which was later improved to $(1+\epsilon, O(k\log(n/\epsilon)))$ and then to $(1, O(k \log n))$ here, Theorem 5.) I'll think about whether we can reduce the number of centers for metric, using those and your ideas. $\endgroup$
    – Neal Young
    Commented Jun 15, 2021 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.