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.STACS.2014.251
URN: urn:nbn:de:0030-drops-44625
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4462/
Cygan, Marek ;
Kociumaka, Tomasz
Constant Factor Approximation for Capacitated k-Center with Outliers
Abstract
The k-center problem is a classic facility location problem, where given an edge-weighted graph G=(V,E) one is to find a subset of k vertices S, such that each vertex in V is "close" to some vertex in S. The approximation status of this basic problem is well understood, as a simple 2-approximation algorithm is known to be tight. Consequently different extensions were studied.
In the capacitated version of the problem each vertex is assigned a capacity, which is a strict upper bound on the number of clients a facility can serve, when located at this vertex. A constant factor approximation for the capacitated k-center was obtained last year in [Cygan, Hajiaghayi and Khuller, FOCS'12], which was recently improved to a 9-approximation in [An, Bhaskara and Svensson, arXiv'13].
In a different generalization of the problem some clients (denoted as outliers) may be disregarded. Here we are additionally given an integer p and the goal is to serve exactly p clients, which the algorithm is free to choose. In [Charikar et al., SODA'01] the authors presented a 3-approximation for the k-center problem with outliers.
In this paper we consider a common generalization of the two extensions previously studied separately, i.e. we work with the capacitated k-center with outliers. We present the first constant factor approximation algorithm with approximation ratio of 25 even for the case of non-uniform hard capacities.
BibTeX - Entry
@InProceedings{cygan_et_al:LIPIcs:2014:4462,
author = {Marek Cygan and Tomasz Kociumaka},
title = {{Constant Factor Approximation for Capacitated k-Center with Outliers}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {251--262},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4462},
URN = {urn:nbn:de:0030-drops-44625},
doi = {10.4230/LIPIcs.STACS.2014.251},
annote = {Keywords: approximation algorithms, k-center, capacities, outliers, LP rounding}
}
|
Keywords: |
|
approximation algorithms, k-center, capacities, outliers, LP rounding |
|
Collection: |
|
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
05.03.2014 |
