Document Open Access Logo

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

Authors Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.1.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Zachary Friggstad
Mohsen Rezapour
Mohammad R. Salavatipour

Cite AsGet BibTex

Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Approximating Connected Facility Location with Lower and Upper Bounds via LP Rounding. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SWAT.2016.1

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.
Keywords
  • Facility Location
  • Approximation Algorithm
  • LP Rounding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Zoë Abrams, Adam Meyerson, Kamesh Munagala, and Serge Plotkin. The integrality gap of capacitated facility location. Technical Report CMU-CS-02-199, Carnegie Mellon University, 2002. Google Scholar
  2. Ankit Aggarwal, Anand Louis, Manisha Bansal, Naveen Garg, Neelima Gupta, Shubham Gupta, and Surabhi Jain. A 3-approximation algorithm for the facility location problem with uniform capacities. Mathematical Programming, 141, 2013. Google Scholar
  3. Sara Ahmadian and Chaitanya Swamy. Improved approximation guarantees for lower-bounded facility location. In proceedings of WAOA 2012, pages 257-271, 2012. Google Scholar
  4. Hyung-Chan An, Monika Singh, and Ola Svensson. LP-based algorithms for capacitated facility location. In proceedings of FOCS 2014, pages 256-265, 2014. Google Scholar
  5. Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In proceedings of ESA 2012, pages 133-144, 2012. Google Scholar
  6. Fabián A Chudak and David P Williamson. Improved approximation algorithms for capacitated facility location problems. Mathematical programming, 102, 2005. Google Scholar
  7. Friedrich Eisenbrand, Fabrizio Grandoni, Thomas Rothvoß, and Guido Schäfer. Connected facility location via random facility sampling and core detouring. Journal of Computer and System Sciences, 76(8):709-726, 2010. Google Scholar
  8. Fabrizio Grandoni and Thomas Rothvoß. Approximation algorithms for single and multi-commodity connected facility location. In proceedings of IPCO 2011, pages 248-260, 2011. Google Scholar
  9. Sudipto Guha, Adam Meyerson, and Kamesh Munagala. Hierarchical placement and network design problems. In proceedings of FOCS 2000, pages 603-612, 2000. Google Scholar
  10. Anupam Gupta, Jon Kleinberg, Amit Kumar, Rajeev Rastogi, and Bulent Yener. Provisioning a virtual private network: a network design problem for multicommodity flow. In proceedings of STOC 2001, pages 389-398, 2001. Google Scholar
  11. Hyunwoo Jung, Mohammad Khairul Hasan, and Kyung-Yong Chwa. A 6.55 factor primal-dual approximation algorithm for the connected facility location problem. Journal of combinatorial optimization, 18(3):258-271, 2009. Google Scholar
  12. DR Karget and Maria Minkoff. Building steiner trees with incomplete global knowledge. In proceedings of FOCS 2000, pages 613-623, 2000. Google Scholar
  13. Madhukar R Korupolu, C Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of algorithms, 2000. Google Scholar
  14. Retsef Levi, David B Shmoys, and Chaitanya Swamy. LP-based approximation algorithms for capacitated facility location. Mathematical programming, 131, 2012. Google Scholar
  15. Shi Li. On uniform capacitated k-median beyond the natural lp relaxation. In proceedings of SODA 2015, pages 696-707, 2015. Google Scholar
  16. Shi Li. Approximating capacitated k-median with (1+ε)k open facilities. In proceedings of SODA 2016, 2016. Google Scholar
  17. Martin Pal, Eva Tardos, and Tom Wexler. Facility location with nonuniform hard capacities. In proceedings of FOCS 2001, pages 329-338, 2001. Google Scholar
  18. David B Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In proceedings of STOC 1997, pages 265-274, 1997. Google Scholar
  19. Zoya Svitkina. Lower-bounded facility location. ACM Transactions on Algorithms (TALG), 6(4):69, 2010. Google Scholar
  20. Chaitanya Swamy and Amit Kumar. Primal-dual algorithms for connected facility location problems. Algorithmica, 40(4):245-269, 2004. Google Scholar
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