An approximation algorithm for uniform capacitated k-median problem with 1 + ϵcapacity violation

Jaroslaw Byrka; Bartosz Rybicki; Sumedha Uniyal

doi:10.1007/978-3-319-33461-5_22

An approximation algorithm for uniform capacitated k-median problem with 1 + ϵcapacity violation

Jaroslaw Byrka, Bartosz Rybicki, Sumedha Uniyal

Not published at Aalto University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

15 Citations (Scopus)

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 + ϵ 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 + ϵ. 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.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings
Pages	262-274
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-319-33461-5_22
Publication status	Published - 2016
MoE publication type	A4 Article in a conference publication
Event	International Conference on Integer Programming and Combinatorial Optimization - Liege, Belgium Duration: 1 Jun 2016 → 3 Jun 2016 Conference number: 18

Conference

Conference	International Conference on Integer Programming and Combinatorial Optimization
Abbreviated title	IPCO
Country	Belgium
City	Liege
Period	01/06/2016 → 03/06/2016

Access to Document

10.1007/978-3-319-33461-5_22

Fingerprint Dive into the research topics of 'An approximation algorithm for uniform capacitated k-median problem with 1 + ϵcapacity violation'. Together they form a unique fingerprint.

Cite this

@inproceedings{ca03540659cc4e7ebed9a933bbe9823c,

title = "An approximation algorithm for uniform capacitated k-median problem with 1 + ϵ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 + ϵ 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 + ϵ. 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.",

author = "Jaroslaw Byrka and Bartosz Rybicki and Sumedha Uniyal",

year = "2016",

doi = "10.1007/978-3-319-33461-5_22",

language = "English",

isbn = "9783319334608",

pages = "262--274",

booktitle = "Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings",

note = "International Conference on Integer Programming and Combinatorial Optimization, IPCO ; Conference date: 01-06-2016 Through 03-06-2016",

}

Byrka, J, Rybicki, B & Uniyal, S 2016, An approximation algorithm for uniform capacitated k-median problem with 1 + ϵcapacity violation. in Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings. pp. 262-274, International Conference on Integer Programming and Combinatorial Optimization, Liege, Belgium, 01/06/2016. https://doi.org/10.1007/978-3-319-33461-5_22

An approximation algorithm for uniform capacitated k-median problem with 1 + ϵcapacity violation. / Byrka, Jaroslaw; Rybicki, Bartosz; Uniyal, Sumedha.

Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings. 2016. p. 262-274.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - An approximation algorithm for uniform capacitated k-median problem with 1 + ϵcapacity violation

AU - Byrka, Jaroslaw

AU - Rybicki, Bartosz

AU - Uniyal, Sumedha

N1 - Conference code: 18

PY - 2016

Y1 - 2016

N2 - 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 by a factor of 1 + ϵ. 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.

AB - 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 by a factor of 1 + ϵ. 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.

U2 - 10.1007/978-3-319-33461-5_22

DO - 10.1007/978-3-319-33461-5_22

M3 - Conference contribution

SN - 9783319334608

SP - 262

EP - 274

BT - Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings

T2 - International Conference on Integer Programming and Combinatorial Optimization

Y2 - 1 June 2016 through 3 June 2016

ER -