zbMATH — the first resource for mathematics

Capacitated \(k\)-center problem with vertex weights. (English) Zbl 1391.68042
Lal, Akash (ed.) et al., 36th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2016), Chennai, India, December 13–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-027-9). LIPIcs – Leibniz International Proceedings in Informatics 65, Article 8, 14 p. (2016).
Summary: 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-\varepsilon}\)-approximation hardness for this problem, for any \(\varepsilon>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 \(\mathrm{P}=\mathrm{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-\varepsilon}\)-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.
For the entire collection see [Zbl 1354.68012].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68W25 Approximation algorithms
90B80 Discrete location and assignment
Full Text: DOI