Document Open Access Logo

Approximating Activation Edge-Cover and Facility Location Problems

Authors Zeev Nutov, Guy Kortsarz, Eli Shalom

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2019.20.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Zeev Nutov
  • The Open University of Israel, Ra’anana, Israel
Guy Kortsarz
  • Rutgers University, Camden, USA
Eli Shalom
  • The Open University of Israel, Ra’anana, Israel

Funding

  • Kortsarz, Guy: Partially supported by NSF grant number 1540547.

Acknowledgements

We thank anonymous referees for many useful comments.

Cite As Get BibTex

Zeev Nutov, Guy Kortsarz, and Eli Shalom. Approximating Activation Edge-Cover and Facility Location Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.MFCS.2019.20

Abstract

What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V,E), a set R subseteq V of terminals, and thresholds {t^e_u,t^e_v} for each uv-edge e in E. The goal is to find an assignment a={a_v:v in V} to the nodes minimizing sum_{v in V} a_v, such that the edge set E_a={e=uv: a_u >= t^e_u, a_v >= t^e_v} activated by a covers R. We obtain ratio 1+max_{x>=1}(ln x)/(1+x/theta)~= ln theta - ln ln theta for the problem, where theta is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of {Facility Location}. If for each facility all service costs are identical then we show a better ratio 1+max_{k in N}(H_k-1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1.406 of [Calinescu et al, 2019] (achieved by iterative randomized rounding) to 1.2785. For unit thresholds we improve the ratio 73/60~=1.217 of [Calinescu et al, 2019] to 1555/1347~=1.155.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
Keywords
  • generalized min-covering problem
  • activation edge-cover
  • facility location
  • minimum power
  • approximation algorithm

Metrics

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

References

  1. S. Athanassopoulos, I. Caragiannis, and C. Kaklamanis. Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs. Theory Comput. Syst., 45(3):555-576, 2009. Google Scholar
  2. Reuven Bar-Yehuda. One for the price of two: A unified approach for approximating covering problems. Algorithmica, 27(2):131-144, 2000. Google Scholar
  3. J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM, 60(1):6:1-6:33, 2013. Google Scholar
  4. G. Calinescu, G. Kortsarz, and Z. Nutov. Improved approximation algorithms for minimum power covering problems. In WAOA, pages 134-148, 2018. Google Scholar
  5. K. Chandrasekaran, R. M. Karp, E. Moreno-Centeno, and S. Vempala. Algorithms for Implicit Hitting Set Problems. In SODA, pages 614-629, 2011. Google Scholar
  6. V. Chvatal. Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 4(3):233-235, 1979. Google Scholar
  7. R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth. On the Lambert W function. Advances in Computational Mathematics, 5:329-359, 1996. Google Scholar
  8. Rong-chii Duh and Martin Fürer. Approximation of k-set cover by semi-local optimization. In STOC, pages 256-264, 1997. Google Scholar
  9. J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449-467, 1965. Google Scholar
  10. U. Feige. A threshold of ln n for approximating set cover. J. of the ACM, 45(4):634-652, 1998. Google Scholar
  11. M. Fürer and H. Yu. Packing-Based Approximation Algorithm for the k-Set Cover Problem. In ISAAC, pages 484-493, 2011. Google Scholar
  12. M. X. Goemans, N. Olver, T. Rothvoß, and R. Zenklusen. Matroids and integrality gaps for hypergraphic steiner tree relaxations. In STOC, pages 1161-1176, 2012. Google Scholar
  13. C. Gröpl, S. Hougardy, T. Nierhoff, and H. J. Prömel. Approximation Algorithms for the Steiner Tree Problem in Graphs. In X. Z. Cheng and D-. Z. Du, editors, Steiner Trees in Industry, pages 235-279. Kluwer Academic Publishers, 2001. Google Scholar
  14. M. Hajiaghayi, G. Kortsarz, V. Mirrokni, and Z. Nutov. Power optimization for connectivity problems. Math. Programming, 110(1):195-208, 2007. Google Scholar
  15. A. Hoorfar and M. Hassani. Inequalities on the Lambert W Function and Hyperpower Function. Journal of Inequalities in Pure and Applied Mathematics (IPAM), 9(2), 2008. Article 51, 5 pp. Google Scholar
  16. D. S. Johnson. Approximation Algorithms for Combinatorial Problems. J. Comput. Syst. Sci., 9(3):256-278, 1974. Google Scholar
  17. G. Kortsarz and Z. Nutov. Approximating minimum-power edge-covers and 2,3-connectivity. Discrete Applied Mathematics, 157:1840-1847, 2009. Google Scholar
  18. A. Levin. Approximating the unweighted k-set cover problem: greedy meets local search. In WAOA, pages 290-301, 2006. Google Scholar
  19. Z. Nutov. Activation Network Design Problems. In T. F. Gonzalez, editor, Handbook on Approximation Algorithms and Metaheuristics, Second Edition, volume 2, chapter 15. Chapman & Hall/CRC, 2018. Google Scholar
  20. D. Panigrahi. Survivable Network Design Problems in Wireless Networks. In SODA, pages 1014-1027, 2011. Google Scholar
  21. R. Raz and S. Safra. A sub constant error probability low degree test, and a sub constant error probability PCP characterization of NP. In STOC, pages 475-484, 1997. Google Scholar
  22. G. Robins and A. Zelikovsky. Tighter Bounds for Graph Steiner Tree Approximation. SIAM J. Discrete Math., 19(1):122-134, 2005. Google Scholar
  23. A. Schrijver. Combinatorial Optimization, Polyhedra and Efficiency. Springer-Verlag Berlin, Heidelberg New York, 2004. Google Scholar
  24. D B. Shmoys. Approximation algorithms for facility location problems. In APPROX, pages 265-274, 2000. Google Scholar
  25. P. Slavik. A Tight Analysis of the Greedy Algorithm for Set Cover. J. Algorithms, 25(2):237-254, 1997. Google Scholar
  26. J. Vygen. Approximation algorithms for facility location problems (Lecture Notes). Technical Report 05950, Research Institute for Discrete Mathematics, University of Bonn, 2005. Google Scholar
  27. L. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982. Google Scholar
  28. N. E. Young. Greedy Set-Cover Algorithms. In Encyclopedia of Algorithms, pages 886-889. Springer, 2016. 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 About DROPS Imprint Privacy Contact