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

Question

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.

Answer 1

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$

Answer 2

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.