Perturbation resilient clustering for κ-Center and related problems via lp relaxations

Chandra Chekuri, Shalmoli Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider clustering in the perturbation resilience model that has been studied since the work of Bilu and Linial [16] and Awasthi, Blum and Sheffet [8]. A clustering instance I is said to be α-perturbation resilient if the optimal solution does not change when the pairwise distances are modified by a factor of α and the perturbed distances satisfy the metric property-this is the metric perturbation resilience property introduced in [4] and a weaker requirement than prior models. We make two high-level contributions. We show that the natural LP relaxation of κ-center and asymmetric κ-center is integral for 2-perturbation resilient instances. We belive that demonstrating the goodness of standard LP relaxations complements existing results [12, 4] that are based on new algorithms designed for the perturbation model. We define a simple new model of perturbation resilience for clustering with outliers. Using this model we show that the unified MST and dynamic programming based algorithm proposed in [4] exactly solves the clustering with outliers problem for several common center based objectives (like κ-center, κ-means, κ-median) when the instances is 2-perturbation resilient. We further show that a natural LP relxation is integral for 2-perturbation resilient instances of κ-center with outliers.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
EditorsEric Blais, Jose D. P. Rolim, David Steurer, Klaus Jansen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770859
DOIs
StatePublished - Aug 1 2018
Event21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 - Princeton, United States
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume116
ISSN (Print)1868-8969

Other

Other21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
CountryUnited States
CityPrinceton
Period8/20/188/22/18

Keywords

  • Beyond Worst Case Analysis
  • Clustering
  • LP Integrality
  • Outliers
  • Perturbation Resilience

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Perturbation resilient clustering for κ-Center and related problems via lp relaxations'. Together they form a unique fingerprint.

  • Cite this

    Chekuri, C., & Gupta, S. (2018). Perturbation resilient clustering for κ-Center and related problems via lp relaxations. In E. Blais, J. D. P. Rolim, D. Steurer, & K. Jansen (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018 [9] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 116). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.9