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.FSTTCS.2016.8
URN: urn:nbn:de:0030-drops-68438
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6843/
 Go to the corresponding LIPIcs Volume Portal

### Capacitated k-Center Problem with Vertex Weights

 pdf-format:

### Abstract

We study the capacitated k-center problem with vertex weights. It is a generalization of the well known k-center 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^{1-epsilon}-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 k-center 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 super-constant inapproximability result. The hardness result easily generalizes to versions of the problem that consider the p-norm 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 n-approximation algorithm for this problem. We also give a bi-criteria 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 k-Center Problem with Vertex Weights}},
booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages =	{8:1--8:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-027-9},
ISSN =	{1868-8969},
year =	{2016},
volume =	{65},
editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6843},
URN =		{urn:nbn:de:0030-drops-68438},
doi =		{10.4230/LIPIcs.FSTTCS.2016.8},
annote =	{Keywords: approximation hardness, k-center, gadget reduction}
}
```

 Keywords: approximation hardness, k-center, gadget reduction Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) Issue Date: 2016 Date of publication: 10.12.2016

DROPS-Home | Fulltext Search | Imprint | Privacy