An Approximation Algorithm for Uniform Capacitated k-Median Problem with Capacity Violation
International Conference on Integer Programming and Combinatorial Optimization, 2016•Springer
We study the Capacitated k-Median problem, for which all the known constant factor
approximation algorithms violate either the number of facilities or the capacities. While the
standard LP-relaxation can only be used for algorithms violating one of the two by a factor of
at least two, Li 10, 11 gave algorithms violating the number of facilities by a factor of 1+ ϵ
exploring properties of extended relaxations. In this paper we develop a constant factor
approximation algorithm for hard Uniform Capacitated k-Median violating only the capacities …
approximation algorithms violate either the number of facilities or the capacities. While the
standard LP-relaxation can only be used for algorithms violating one of the two by a factor of
at least two, Li 10, 11 gave algorithms violating the number of facilities by a factor of 1+ ϵ
exploring properties of extended relaxations. In this paper we develop a constant factor
approximation algorithm for hard Uniform Capacitated k-Median violating only the capacities …
Abstract
We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of the two by a factor of at least two, Li [10, 11] gave algorithms violating the number of facilities by a factor of exploring properties of extended relaxations.
In this paper we develop a constant factor approximation algorithm for hard Uniform Capacitated k-Median violating only the capacities by a factor of . The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果