LIPIcs.APPROX-RANDOM.2020.57.pdf
- Filesize: 0.6 MB
- 19 pages
Document
Approximating Star Cover Problems
Authors
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-08-11
File
Document Identifiers
Acknowledgements
We are very grateful to Ola Svensson for influential discussions at multiple stages of this work.
Cite As Get BibTex
Buddhima Gamlath and Vadim Grinberg. Approximating Star Cover Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.57
Abstract
Given a metric space (F ∪ C, d), we consider star covers of C with balanced loads. A star is a pair (i, C_i) where i ∈ F and C_i ⊆ C, and the load of a star is ∑_{j ∈ C_i} d(i, j). In minimum load k-star cover problem (MLkSC), one tries to cover the set of clients C using k stars that minimize the maximum load of a star, and in minimum size star cover (MSSC) one aims to find the minimum number of stars of load at most T needed to cover C, where T is a given parameter.
We obtain new bicriteria approximations for the two problems using novel rounding algorithms for their standard LP relaxations. For MLkSC, we find a star cover with (1+O(ε))k stars and O(1/ε²)OPT_MLk load where OPT_MLk is the optimum load. For MSSC, we find a star cover with O(1/ε²) OPT_MS stars of load at most (2 + O(ε)) T where OPT_MS is the optimal number of stars for the problem. Previously, non-trivial bicriteria approximations were known only when F = C.
Subject Classification
ACM Subject Classification
- Theory of computation
Keywords
- star cover
- approximation algorithms
- lp rounding
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad R. Salavatipour, and Chaitanya Swamy. Approximation algorithms for minimum-load k-facility location. ACM Transactions on Algorithms, 14(2):16:1-16:29, 2018. URL: http://doi.org/10.1145/3173047.
- Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. In Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 61-72, 2017. URL: http://doi.org/10.1109/FOCS.2017.15.
- Esther M. Arkin, Refael Hassin, and Asaf Levin. Approximations for minimum and min-max vehicle routing problems. Journal of Algorithms, 59(1):1-18, 2006. URL: https://doi.org/10.1016/j.jalgor.2005.01.007.
- Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2):23:1-23:31, 2017. URL: http://doi.org/10.1145/2981561.
- Guy Even, Naveen Garg, Jochen Könemann, R. Ravi, and Amitabh Sinha. Covering graphs using trees and stars. In Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003, 2003. URL: https://doi.org/10.1007/978-3-540-45198-3_3.
- M. Reza Khani and Mohammad R. Salavatipour. Improved approximation algorithms for the min-max tree cover and bounded tree cover problems. Algorithmica, 69:302-314, 2014. URL: https://doi.org/10.1007/s00453-012-9740-5.
- Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, 46(1):259-271, 1990. URL: https://doi.org/10.1007/BF01585745.
- Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. In Proceedings of the 38th International Colloquium on Automata, Languages and Programming, ICALP 2011, pages 45-58, 2013. URL: https://doi.org/10.1016/j.ic.2012.01.007.
- Jyh-Han Lin and Jeffrey Scott Vitter. e-approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992, pages 771-782, 1992. URL: https://doi.org/10.1145/129712.129787.
- David B. Shmoys and Éva Tardos. Scheduling unrelated machines with costs. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1993, pages 448-454, 1993. URL: https://dl.acm.org/doi/10.5555/313559.313851.