2026-07-23T07:36:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6211 2024-03-06T10:37:47Z ddc:004 open_access

Constant Approximation for Capacitated k-Median with (1+epsilon)-Capacity Violation Demirci, Gökalp Li, Shi Approximation Algorithms Capacitated k-Median Pseudo Approximation Capacity Violation We study the Capacitated k-Median problem for which existing constant-factor approximation algorithms are all pseudo-approximations that violate either the capacities or the upper bound k on the number of open facilities. Using the natural LP relaxation for the problem, one can only hope to get the violation factor down to 2. Li [SODA'16] introduced a novel LP to go beyond the limit of 2 and gave a constant-factor approximation algorithm that opens (1 + epsilon)*k facilities. We use the configuration LP of Li [SODA'16] to give a constant-factor approximation for the Capacitated k-Median problem in a seemingly harder configuration: we violate only the capacities by 1 + epsilon. This result settles the problem as far as pseudo-approximation algorithms are concerned. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gökalp Demirci and Shi Li 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.73 urn:nbn:de:0030-drops-62112 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.73 eng https://creativecommons.org/licenses/by/3.0/legalcode