Robust k-center with two types of radii

• 成果类型: Article
• 署名作者: Chakrabarty, Deeparnab; Negahbani, Maryam
• 署名单位: Dartmouth College
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01799-3
• 发表日期: 2023
• 页码: 991-1007
• 关键词: algorithms

摘要

In the non-uniform k-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.