LIPIcs.FSTTCS.2018.24.pdf
- Filesize: 457 kB
- 12 pages
Document
A 5-Approximation for Universal Facility Location
Authors
-
Part of:
Volume:
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-12-05
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.24
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.
Subject Classification
ACM Subject Classification
- General and reference → Reference works
- General and reference → General conference proceedings
- Theory of computation → Facility location and clustering
Keywords
- Facility location
- Approximation Algorithms
- Local Search
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Eric Angel, Nguyen Kim Thang, and Damien Regnault. Improved Local Search for Universal Facility Location. In Proceedings of 19th International Conference on Computing and Combinatorics (COCOON), Hangzhou, China, pages 316-324, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38768-5_29.
-
Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-Approximation for Capacitated Facility Location. In Algorithms - ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings, pages 133-144, 2012.
- Mohammad Mahdian and Martin Pál. Universal Facility Location. In Proceedings of the 11th Annual European Symposium on Algorithms (ESA), Budapest, Hungary, volume 2832 of Lecture Notes in Computer Science, pages 409-421, 2003. URL: http://dx.doi.org/10.1007/978-3-540-39658-1_38.
-
M. Pál, É. Tardos, and T. Wexler. Facility Location with Nonuniform Hard Capacities. In FOCS '01: Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, page 329, Washington, DC, USA, 2001. IEEE Computer Society.
- Jens Vygen. From stars to comets: Improved local search for universal facility location. Journal of Operations Research Letters, 35(4):427-433, 2007. URL: http://dx.doi.org/10.1016/j.orl.2006.08.004.
- Jiawei Zhang, Bo Chen, and Yinyu Ye. A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem. Math. Oper. Res., 30(2):389-403, 2005. URL: http://dx.doi.org/10.1287/moor.1040.0125.