License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.31
URN: urn:nbn:de:0030-drops-126347
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12634/
Go to the corresponding LIPIcs Volume Portal

Bandyapadhyay, Sayan

On Perturbation Resilience of Non-Uniform k-Center

pdf-format:
LIPIcs-APPROX31.pdf (0.6 MB)

Abstract

The Non-Uniform k-center (NUkC) problem has recently been formulated by Chakrabarty, Goyal and Krishnaswamy [ICALP, 2016] as a generalization of the classical k-center clustering problem. In NUkC, given a set of n points P in a metric space and non-negative numbers r₁, r₂, … , r_k, the goal is to find the minimum dilation α and to choose k balls centered at the points of P with radius α⋅ r_i for 1 ≤ i ≤ k, such that all points of P are contained in the union of the chosen balls. They showed that the problem is NP-hard to approximate within any factor even in tree metrics. On the other hand, they designed a "bi-criteria" constant approximation algorithm that uses a constant times k balls. Surprisingly, no true approximation is known even in the special case when the r_i’s belong to a fixed set of size 3. In this paper, we study the NUkC problem under perturbation resilience, which was introduced by Bilu and Linial [Combinatorics, Probability and Computing, 2012]. We show that the problem under 2-perturbation resilience is polynomial time solvable when the r_i’s belong to a constant sized set. However, we show that perturbation resilience does not help in the general case. In particular, our findings imply that even with perturbation resilience one cannot hope to find any "good" approximation for the problem.

BibTeX - Entry

@InProceedings{bandyapadhyay:LIPIcs:2020:12634,
  author =	{Sayan Bandyapadhyay},
  title =	{{On Perturbation Resilience of Non-Uniform k-Center}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12634},
  URN =		{urn:nbn:de:0030-drops-126347},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.31},
  annote =	{Keywords: Non-Uniform k-center, stability, clustering, perturbation resilience}
}

Keywords: Non-Uniform k-center, stability, clustering, perturbation resilience
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI