Document Open Access Logo

Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem

Authors Kangsan Kim, Yongho Shin, Hyung-Chan An

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.21.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Kangsan Kim
  • Devsisters Corp., Seoul, South Korea
Yongho Shin
  • Department of Computer Science, Yonsei University, Seoul, South Korea
Hyung-Chan An
  • Department of Computer Science, Yonsei University, Seoul, South Korea

Funding

This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2019R1C1C1008934). This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2016R1C1B1012910). This research was supported by the Yonsei University Research Fund of 2018-22-0093.

Acknowledgements

We thank the anonymous reviewers of this paper for their helpful comments.

Cite AsGet BibTex

Kangsan Kim, Yongho Shin, and Hyung-Chan An. Constant-Factor Approximation Algorithms for the Parity-Constrained Facility Location Problem. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.21

Abstract

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement - odd, even, or unconstrained - of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Facility location and clustering
Keywords
  • Facility location problems
  • approximation algorithms
  • clustering problems
  • parity constraints

Metrics

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

References

  1. Anna Adamaszek, Antonios Antoniadis, Amit Kumar, and Tobias Mömke. Approximating airports and railways. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1-5:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2018.5.
  2. Mustaque Ahamad and Mostafa H. Ammar. Performance characterization of quorum-consensus algorithms for replicated data. IEEE Transactions on Software Engineering, 15(4):492-496, 1989. Google Scholar
  3. Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. Local-search based approximation algorithms for mobile facility location problems. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1607-1621, 2013. URL: http://dl.acm.org/citation.cfm?id=2627817.2627932.
  4. Hyung-Chan An, Mohit Singh, and Ola Svensson. LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1):272-306, 2017. Google Scholar
  5. Michel L. Balinski. On finding integer solutions to linear programs. Technical report, Mathematica Princeton NJ, 1964. Google Scholar
  6. Manisha Bansal, Naveen Garg, and Neelima Gupta. A 5-approximation for capacitated facility location. In European Symposium on Algorithms (ESA), pages 133-144, 2012. Google Scholar
  7. András A. Benczúr and Ottilia Fülöp. Fast algorithms for even/odd minimum cuts and generalizations. In European Symposium on Algorithms (ESA), pages 88-99, 2000. Google Scholar
  8. Jaroslaw Byrka. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 29-43. Springer Berlin Heidelberg, Berlin, Heidelberg, 2007. Google Scholar
  9. Joseph Cheriyan, Zachary Friggstad, and Zhihan Gao. Approximating minimum-cost connected T-joins. Algorithmica, 72(1):126-147, 2015. URL: https://doi.org/10.1007/s00453-013-9850-8.
  10. Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online facility location with deletions. In European Symposium on Algorithms (ESA), pages 21:1-21:15, 2018. Google Scholar
  11. Jack Edmonds and Ellis Johnson. Matching, Euler tours and the Chinese postman. Mathematical Programming, 5:88-124, 1973. URL: https://doi.org/10.1007/BF01580113.
  12. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In Automata, Languages, and Programming, pages 459-470, 2014. Google Scholar
  13. Hazel Everett, Celina M.H. de Figueiredo, Cláudia Linhares-Sales, Frédéric Maffray, Oscar Porto, and Bruce A. Reed. Path parity and perfection. Discrete Mathematics, 165:233-252, 1997. Google Scholar
  14. Gramoz Goranci, Monika Henzinger, and Dariusz Leniowski. A tree structure for dynamic facility location. In European Symposium on Algorithms (ESA), pages 39:1-39:13, 2018. Google Scholar
  15. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  16. Martin Grötschel, László Lovász, and Alexander Schrijver. Corrigendum to our paper "the ellipsoid method and its consequences in combinatorial optimization". Combinatorica, 4(4):291-295, 1984. Google Scholar
  17. Martin Grötschel and William R. Pulleyblank. Weakly bipartite graphs and the max-cut problem. Operations Research Letters, 1(1):23-27, 1981. Google Scholar
  18. Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In ACM Symposium on Theory of Computing (STOC), pages 731-740, 2002. Google Scholar
  19. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. Google Scholar
  20. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi. Erdős-Pósa property and its algorithmic applications - parity constraints, subset feedback set, and subset packing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1726-1736, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095253.
  21. Marcin Kaminski and Naomi Nishimura. Finding an induced path of given parity in planar graphs in polynomial time. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 656-670, 2012. URL: https://doi.org/10.1137/1.9781611973099.55.
  22. Madhukar R. Korupolu, C.Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. Journal of Algorithms, 37(1):146-188, 2000. URL: https://doi.org/10.1006/jagm.2000.1100.
  23. Alfred A. Kuehn and Michael J. Hamburger. A heuristic program for locating warehouses. Management Science, 9(4):643-666, 1963. URL: http://www.jstor.org/stable/2627368.
  24. Christiane Lammersen and Christian Sohler. Facility location in dynamic geometric data streams. In European Symposium on Algorithms (ESA), pages 660-671, 2008. Google Scholar
  25. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. In Automata, Languages and Programming, pages 77-88, 2011. Google Scholar
  26. Shi Li. On facility location with general lower bounds. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2279-2290, 2019. Google Scholar
  27. Alan S. Manne. Plant location under economies-of-scale - decentralization and computation. Management Science, 11(2):213-235, 1964. URL: http://www.jstor.org/stable/2627598.
  28. Dániel Marx and Michał Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In European Symposium on Algorithms (ESA), pages 865-877, 2015. Google Scholar
  29. Jens Maßberg and Jens Vygen. Approximation algorithms for a facility location problem with service capacities. ACM Trans. Algorithms, 4(4):50:1-50:15, 2008. URL: https://doi.org/10.1145/1383369.1383381.
  30. Jannik Matuschke, Andreas Bley, and Benjamin Müller. Approximation algorithms for facility location with capacitated and length-bounded tree connections. In Hans L. Bodlaender and Giuseppe F. Italiano, editors, Algorithms - ESA 2013, pages 707-718, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. Google Scholar
  31. Manfred W. Padberg and M. R. Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67-80, 1982. Google Scholar
  32. Martin Pál, Éva Tardos, and Tom Wexler. Facility location with nonuniform hard capacities. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 329-338, 2001. URL: https://doi.org/10.1109/SFCS.2001.959907.
  33. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer Science & Business Media, 2003. Google Scholar
  34. Alexander Schrijver and Paul Seymour. Packing odd paths. Journal of Combinatorial Theory, 62:280-288, 1994. Google Scholar
  35. András Sebő. Eight-fifth approximation for the path TSP. In Integer Programming and Combinatorial Optimization (IPCO), pages 362-374, 2013. Google Scholar
  36. David B. Shmoys and Karen I. Aardal. Approximation algorithms for facility location problems. Utrecht University: Information and Computing Sciences, 1997. Google Scholar
  37. John F. Stollsteimer. A working model for plant numbers and locations. Journal of Farm Economics, 45(3):631-645, 1963. URL: http://www.jstor.org/stable/1235442.
  38. The Apache Software Foundation. Apache ZooKeeper. URL: http://zookeeper.apache.org/.
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