License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.325
URN: urn:nbn:de:0030-drops-47062
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4706/
Go to the corresponding LIPIcs Volume Portal

Li, Shanfei

An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem

pdf-format:
23.pdf (0.6 MB)

Abstract

In the k-median problem, given a set of locations, the goal is to select a subset of at most k centers so as to minimize the total cost of connecting each location to its nearest center. We study the uniform hard capacitated version of the k-median problem, in which each selected center can only serve a limited number of locations.

Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys,
we give an improved approximation algorithm for this problem with increasing the capacities by a constant factor, which improves the previous best approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase.

BibTeX - Entry

@InProceedings{li:LIPIcs:2014:4706,
  author =	{Shanfei Li},
  title =	{{An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{325--338},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4706},
  URN =		{urn:nbn:de:0030-drops-47062},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.325},
  annote =	{Keywords: Approximation algorithm; k-median problem; LP-rounding; Hard capacities}
}

Keywords: Approximation algorithm; k-median problem; LP-rounding; Hard capacities
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI