Approximating k-center in planar graphs
Approximating k-center in planar graphs
复制标题
平面图中的近似 k 中心
DOI：
10.1137/1.9781611973402.47
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Claire Mathieu
中科院分区：
文献类型：
--
作者：
David Eisenstat;P. Klein;Claire Mathieu
我们考虑度量k中心问题的变体。假设您必须在一个城市中为k个消防站选择位置，以便使房屋到最近的消防站的最大距离最小。实例由具有任意非负边长度的图、可以作为消防站（即中心）的一组顶点和代表房屋的一组顶点指定。对于一般图，这个问题完全等价于度量k中心问题，它是apx困难的。给出了输入图为平面图时的多项式时间双准则逼近格式。
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.