# Is there any Bi-criteria PTAS for Metric $k$-Median?

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.

• Are you asking for a polynomial-time algorithm? Jun 15, 2021 at 2:15
• @NealYoung That was an important point. I have edited the question. Thank You! Jun 15, 2021 at 3:14
• 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 Jun 15, 2021 at 12:37

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$$

• 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. Jun 15, 2021 at 16:46
• 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. Jun 15, 2021 at 17:07
• @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. :-) Jun 15, 2021 at 17:52
• 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. Jun 15, 2021 at 21:06
• 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))$. 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.

• 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. Jun 15, 2021 at 13:38