Name
Abstract | ||
|---|---|---|
We consider variants of the metric k-center problem. Imagine that you must choose locations for k firehouses in a city so as to minimize the maximum distance of a house from the nearest firehouse. An instance is specified by a graph with arbitrary nonnegative edge lengths, a set of vertices that can serve as firehouses (i.e., centers) and a set of vertices that represent houses. For general graphs, this problem is exactly equivalent to the metric k-center problem, which is APX-hard. We give a polynomial-time bicriteria approximation scheme when the input graph is a planar graph. We also give polynomial-time bicriteria approximation schemes for several generalizations: if, instead of all houses, we wish to cover a specified proportion of the houses; if the candidate locations for firehouses have rental costs and we wish to minimize not the number of firehouses but the sum of their rental costs; and if the input graph is not planar but is of bounded genus. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.5555/2634074.2634121 | SODA |
Keywords | DocType | ISBN |
algorithms,design,graph algorithms,graph labeling,theory | Conference | 978-1-61197-338-9 |
Citations | PageRank | References |
5 | 0.43 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Eisenstat | 1 | 285 | 19.59 |
| Philip N. Klein | 2 | 2681 | 256.19 |
| Claire Mathieu | 3 | 452 | 25.78 |