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.SWAT.2016.1
URN: urn:nbn:de:0030-drops-60302
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6030/
Go to the corresponding LIPIcs Volume Portal

Friggstad, Zachary ; Rezapour, Mohsen ; Salavatipour, Mohammad R.

Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding

pdf-format:
LIPIcs-SWAT-2016-1.pdf (0.5 MB)

Abstract

We consider a lower- and upper-bounded generalization of the classical facility location problem, where each facility has a capacity (upper bound) that limits the number of clients it can serve and a lower bound on the number of clients it must serve if it is opened. We develop an LP rounding framework that exploits a Voronoi diagram-based clustering approach to derive the first bicriteria constant approximation algorithm for this problem with non-uniform lower bounds and uniform upper bounds. This naturally leads to the the first LP-based approximation algorithm for the lower bounded facility location problem (with non-uniform lower bounds).

We also demonstrate the versatility of our framework by extending this and presenting the first constant approximation algorithm for some connected variant of the problems in which the facilities are required to be connected as well.

BibTeX - Entry

@InProceedings{friggstad_et_al:LIPIcs:2016:6030,
  author =	{Zachary Friggstad and Mohsen Rezapour and Mohammad R. Salavatipour},
  title =	{{Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{1:1--1:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6030},
  URN =		{urn:nbn:de:0030-drops-60302},
  doi =		{10.4230/LIPIcs.SWAT.2016.1},
  annote =	{Keywords: Facility Location, Approximation Algorithm, LP Rounding}
}

Keywords: Facility Location, Approximation Algorithm, LP Rounding
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

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