Kumar, Aounon
Capacitated kCenter Problem with Vertex Weights
Abstract
We study the capacitated kcenter problem with vertex weights. It is a generalization of the well known kcenter problem. In this variant each vertex has a weight and a capacity. The assignment cost of a vertex to a center is given by the product of the weight of the vertex and its distance to
the center. The distances are assumed to form a metric. Each center can only serve as many vertices as its capacity. We show an n^{1epsilon}approximation hardness for this problem, for any epsilon > 0, where n is the number of vertices in the input. Both the capacitated and the weighted versions of the kcenter problem individually can be approximated within a constant factor. Yet the common extension of both the generalizations cannot be approximated efficiently within a constant factor, unless P = NP. This problem, to the best of our knowledge, is the first facility location problem with metric distances known to have a superconstant inapproximability result. The hardness result easily generalizes to versions of the problem that consider the pnorm of the assignment costs (weighted distances) as the objective function. We give n^{1 1/p  epsilon}approximation hardness for this problem, for p>1.
We complement the hardness result by showing a simple napproximation algorithm for this problem. We also give a bicriteria constant factor approximation algorithm, for the case of uniform capacities, which opens at most 2k centers.
BibTeX  Entry
@InProceedings{kumar:LIPIcs:2016:6843,
author = {Aounon Kumar},
title = {{Capacitated kCenter Problem with Vertex Weights}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {8:18:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6843},
URN = {urn:nbn:de:0030drops68438},
doi = {10.4230/LIPIcs.FSTTCS.2016.8},
annote = {Keywords: approximation hardness, kcenter, gadget reduction}
}
2016
Keywords: 

approximation hardness, kcenter, gadget reduction 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

2016 