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].

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].