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.ICALP.2018.30
URN: urn:nbn:de:0030-drops-90345
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9034/
Go to the corresponding LIPIcs Volume Portal

Chakrabarty, Deeparnab ; Negahbani, Maryam

Generalized Center Problems with Outliers

pdf-format:
LIPIcs-ICALP-2018-30.pdf (0.5 MB)

Abstract

We study the F-center problem with outliers: given a metric space (X,d), a general down-closed family F of subsets of X, and a parameter m, we need to locate a subset S in F of centers such that the maximum distance among the closest m points in X to S is minimized.
Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient 3-approximation for the F-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over F subject to a partition constraint. One concrete upshot of our result is a polynomial time 3-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.

BibTeX - Entry

@InProceedings{chakrabarty_et_al:LIPIcs:2018:9034,
  author =	{Deeparnab Chakrabarty and Maryam Negahbani},
  title =	{{Generalized Center Problems with Outliers}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9034},
  URN =		{urn:nbn:de:0030-drops-90345},
  doi =		{10.4230/LIPIcs.ICALP.2018.30},
  annote =	{Keywords: Approximation Algorithms, Clustering, k-Center Problem}
}

Keywords: Approximation Algorithms, Clustering, k-Center Problem
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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