TY - GEN
T1 - Constant approximation for capacitated k-median with (1+ϵ)-capacity violation
AU - Demirci, Gökalp
AU - Li, Shi
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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 + ϵ)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 + ϵ. This result settles the problem as far as pseudo-approximation algorithms are concerned.
AB - 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 + ϵ)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 + ϵ. This result settles the problem as far as pseudo-approximation algorithms are concerned.
KW - Approximation algorithms
KW - Capacitated k-median
KW - Capacity violation
KW - Pseudo approximation
UR - https://www.scopus.com/pages/publications/85012895105
U2 - 10.4230/LIPIcs.ICALP.2016.73
DO - 10.4230/LIPIcs.ICALP.2016.73
M3 - Conference contribution
AN - SCOPUS:85012895105
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
A2 - Rabani, Yuval
A2 - Chatzigiannakis, Ioannis
A2 - Sangiorgi, Davide
A2 - Mitzenmacher, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016
Y2 - 12 July 2016 through 15 July 2016
ER -