Robust k-Center with Two Types of Radii
Robust k-Center with Two Types of Radii
复制标题
具有两种半径的稳健 k 中心
DOI：
10.1007/978-3-030-73879-2_19
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Negahbani, M
中科院分区：
文献类型：
--
作者：
Chakrabarty, D;Negahbani, M
在非均匀中心问题中，目标是用指定数量的不同半径的球覆盖度量空间中的点。 Chakrabarty、Goyal 和 Krishnaswamy [ICALP 2016，Trans。关于阿尔格斯。 2020]（CGK，此后）当有两种类型的半径时给出常数因子近似。在本文中，我们在存在异常值的情况下给出了两个半径情况的常数因子近似。为了实现这一点，我们需要绕过 CGK 方法中不良完整性差距的技术障碍。我们使用“椭球体方法中的椭球体方法”来实现：使用椭球体方法的外层来简化为风格化实例，并使用椭球体方法的内层来解决这些特殊实例。这个想法具有独立意义，可以应用于其他问题。
In the non-uniformk-center problem, the objective is to cover points in a metric space with specified number of balls of different radii. Chakrabarty, Goyal, and Krishnaswamy [ICALP 2016, Trans. on Algs. 2020] (CGK, henceforth) give a constant factor approximation when there are two types of radii. In this paper, we give a constant factor approximation for the two radii case in the presence of outliers. To achieve this, we need to bypass the technical barrier of bad integrality gaps in the CGK approach. We do so using “the ellipsoid method inside the ellipsoid method”: use an outer layer of the ellipsoid method to reduce to stylized instances and use an inner layer of the ellipsoid method to solve these specialized instances. This idea is of independent interest and could be applicable to other problems.