1 Search Results for "Bansal, Manisha"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.24
A 5-Approximation for Universal Facility Location

Authors: Manisha Bansal, Naveen Garg, and Neelima Gupta

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

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.
Cite as

Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-Approximation for Universal Facility Location. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.FSTTCS.2018.24,
  author =	{Bansal, Manisha and Garg, Naveen and Gupta, Neelima},
  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 =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.24},
  URN =		{urn:nbn:de:0030-drops-99239},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.24},
  annote =	{Keywords: Facility location, Approximation Algorithms, Local Search}
}
  • Refine by Author
  • 1 Bansal, Manisha
  • 1 Garg, Naveen
  • 1 Gupta, Neelima

  • Refine by Classification
  • 1 General and reference → General conference proceedings
  • 1 General and reference → Reference works
  • 1 Theory of computation → Facility location and clustering

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Facility location
  • 1 Local Search

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact