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.FSTTCS.2018.24
URN: urn:nbn:de:0030-drops-99239
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9923/
Go to the corresponding LIPIcs Volume Portal

Bansal, Manisha ; Garg, Naveen ; Gupta, Neelima

A 5-Approximation for Universal Facility Location

pdf-format:
LIPIcs-FSTTCS-2018-24.pdf (0.4 MB)

Abstract

In this paper, we propose and analyze a local search algorithm for the Universal facility location problem. Our algorithm improves the approximation ratio of this problem from 5.83, given by Angel et al., to 5. A second major contribution of the paper is that it gets rid of the expensive multi operation that was a mainstay of all previous local search algorithms for capacitated facility location and universal facility location problem. The only operations that we require to prove the 5-approximation are add, open, and close. A multi operation is basically a combination of the open and close operations. The 5-approximation algorithm for the capacitated facility location problem, given by Bansal et al., also uses the multi operation. However, on careful observation, it turned out that add, open, and close operations are sufficient to prove a 5-factor for the problem. This resulted into an improved algorithm for the universal facility location problem, with an improved factor.

BibTeX - Entry

@InProceedings{bansal_et_al:LIPIcs:2018:9923,
  author =	{Manisha Bansal and Naveen Garg and Neelima Gupta},
  title =	{{A 5-Approximation for Universal Facility Location}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{24:1--24:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9923},
  URN =		{urn:nbn:de:0030-drops-99239},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.24},
  annote =	{Keywords: Facility location, Approximation Algorithms, Local Search}
}

Keywords: Facility location, Approximation Algorithms, Local Search
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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