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: https://drops.dagstuhl.de/opus/volltexte/2018/9034/
Chakrabarty, Deeparnab ; Negahbani, Maryam
Generalized Center Problems with Outliers
| pdf-format: |
|
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 | |
| Seminar: | 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 04.07.2018 |
