New Approximability Results for the Robust k-Median Problem
New Approximability Results for the Robust k-Median Problem
复制标题
鲁棒 k 中值问题的新近似性结果
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Adrian Neumann
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;Parinya Chalermsook;K. Mehlhorn;Adrian Neumann
我们考虑一个变种的经典k-中位数问题，介绍了安东尼等人。[1]的文件。在鲁棒k-Median问题中，我们给出一个n-顶点度量空间（V，d）和m个客户集\（\left\{ S_i \subseteq V \right\}_{i=1}^m\）。我们想打开一个k个设施的集合F V，使得所有客户端集合上的最坏情况连接成本最小化;也就是说，最小化\（\max_{i}\sum_{v \in S_i} d（F，v）\）。Anthony等人给出了一个O（logm）的近似算法，适用于任何度量和APX-硬度，即使是在均匀度量的情况下。在本文中，我们通过提供Ω（logm/ loglogm）近似硬度来证明他们的算法是近似紧的，除非\（{\sf NP} \subseteq \bigcap_{\delta >0} {\sf DTIME}（2^{n^{\delta}}）\）。这一结果甚至适用于统一和线度量。据我们所知，这是线性度量问题难以在对数因子内逼近的罕见情况之一。我们补充的硬度结果不同的apricistics的实验评估表明，非常简单的apricistics实现良好的近似现实类的实例。
We consider a variant of the classical k-median problem, introduced by Anthony et al.[1]. In the Robust k-Median problem, we are given an n-vertex metric space (V,d) and m client sets \(\left\{ S_i \subseteq V \right\}_{i=1}^m\). We want to open a set F ⊆ V of k facilities such that the worst case connection cost over all client sets is minimized; that is, minimize \(\max_{i}\sum_{v \in S_i} d(F,v)\). Anthony et al. showed an O(logm) approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing Ω(logm/ loglogm) approximation hardness, unless \({\sf NP} \subseteq \bigcap_{\delta >0} {\sf DTIME}(2^{n^{\delta}})\). This result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances.