Cygan, Marek ;
Kociumaka, Tomasz
Constant Factor Approximation for Capacitated kCenter with Outliers
Abstract
The kcenter problem is a classic facility location problem, where given an edgeweighted 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 2approximation 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 kcenter was obtained last year in [Cygan, Hajiaghayi and Khuller, FOCS'12], which was recently improved to a 9approximation 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 3approximation for the kcenter 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 kcenter with outliers. We present the first constant factor approximation algorithm with approximation ratio of 25 even for the case of nonuniform hard capacities.
BibTeX  Entry
@InProceedings{cygan_et_al:LIPIcs:2014:4462,
author = {Marek Cygan and Tomasz Kociumaka},
title = {{Constant Factor Approximation for Capacitated kCenter with Outliers}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {251262},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897651},
ISSN = {18688969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4462},
URN = {urn:nbn:de:0030drops44625},
doi = {10.4230/LIPIcs.STACS.2014.251},
annote = {Keywords: approximation algorithms, kcenter, capacities, outliers, LP rounding}
}
2014
Keywords: 

approximation algorithms, kcenter, capacities, outliers, LP rounding 
Seminar: 

31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Issue date: 

2014 
Date of publication: 

2014 