Name
Title | ||
|---|---|---|
An Approximation Algorithm for Uniform Capacitated k-Median Problem with 1+\epsilon Capacity Violation. |
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 $$1+\\epsilon $$ 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 $$1\\,+\\,\\epsilon $$. 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-33461-5_22 | IPCO |
Field | DocType | Volume |
Discrete mathematics,Approximation algorithm,Mathematical optimization,Combinatorics,Rounding,Mathematics | Conference | 9682 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.45 |
References | Authors | |
5 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jaroslaw Byrka | 1 | 523 | 31.45 |
| Bartosz Rybicki | 2 | 43 | 4.80 |
| Sumedha Uniyal | 3 | 7 | 0.82 |