Consider the following fire station problem: The input is a positive integer k and a complete undirected graph $G = (V,E)$ with distances on the edges. The distances form a metric: $d(v, v) = 0$, $d(u, v) = d(v, u) ≥ 0$, and $d(u, w) ≤ d(u, v) + d(v, w)$. The output is a subset $S\subset V$ with $|S| \leq k$ such that cost $\sum_{v\in V} \min _{u\in S} d(v,u)$ is minimized. Let $O^*$ be the optimal value of the cost, is it possible to construct a linear program with rounding that runs in polynomial time and approximately solve the problem such that the cost is no more than $(1+\epsilon) O^*$?

  • 1
    $\begingroup$ Isn't this just the metric $k$-median problem? Then, no, it is NP-hard to approximate $k$-median better than a factor of $1 + 2/e$ dl.acm.org/citation.cfm?id=510012. There are constant factor approximation algorithms, some of which do use LP rounding. $\endgroup$ – Sasho Nikolov Oct 26 '15 at 1:10
  • $\begingroup$ Thanks for your help. This is the metric $k$-median problem. Another question is whether I can get better approximation, say $(1+\epsilon )O^*$ with a larger number of $|S|$, say $k\leq |S| \leq n$? $\endgroup$ – Steve Oct 26 '15 at 2:11
  • 1
    $\begingroup$ For (even non-metric) k-medians, if you're willing to open, say, $k\ln n$ facilities, you can achieve assignment cost bounded by the optimal assignment cost using $k$ facilities. $\endgroup$ – Neal Young Dec 28 '15 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.