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

Jaroslaw Byrka, Bartosz Rybicki, Sumedha Uniyal

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-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 languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Proceedings
Pages262-274
Number of pages13
DOIs
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Integer Programming and Combinatorial Optimization - Liege, Belgium
Duration: 1 Jun 20163 Jun 2016
Conference number: 18

Conference

ConferenceInternational Conference on Integer Programming and Combinatorial Optimization
Abbreviated titleIPCO
CountryBelgium
CityLiege
Period01/06/201603/06/2016

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