<p>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^*$?</p>

CC BY-SA 3.0
2015-10-26T01:10:31.017Z
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$ http://dl.acm.org/citation.cfm?id=510012. There are constant factor approximation algorithms, some of which do use LP rounding.
Sasho Nikolov
CC BY-SA 3.0
2015-10-26T02:11:36.067Z
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$?
Steve
CC BY-SA 3.0
2015-12-28T04:18:05.017Z
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.
Neal Young
<cc.complexity-theory><approximation-algorithms><linear-programming>
Linear Programing with Rounding for the Fire Station Problem
Steve
# Linear Programing with Rounding for the Fire Station Problem

(Asked by: username_0 on 2015-10-26)

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^\*$?

**Tags:** cc.complexity-theory, approximation-algorithms, linear-programming

> **Comments:**
> **username_1**: 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$ http://dl.acm.org/citation.cfm?id=510012. There are constant factor approximation algorithms, some of which do use LP rounding.  
> **username_0**: 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$?  
> **username_2**: 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.  

---

## 0 answers

