2026-07-22T10:53:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6843 2024-03-06T10:39:00Z ddc:004 open_access

Capacitated k-Center Problem with Vertex Weights Kumar, Aounon approximation hardness k-center gadget reduction 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aounon Kumar 2016 Is Part Of LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2016.8 urn:nbn:de:0030-drops-68438 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.8 eng https://creativecommons.org/licenses/by/3.0/legalcode