The LP-rounding plus greed approach for partial optimization revisited

Abstract

There are many optimization problems having the following common property: Given a total task consisting of many subtasks, the problem asks to find a solution to complete only part of these subtasks. Examples include the k-Forest problem and the k-Multicut problem, etc. These problems are called partial optimization problems, which are often NP-hard. In this paper, we systematically study the LP-rounding plus greed approach, a method to design approximation algorithms for partial optimization problems. The approach is simple, powerful and versatile. We show how to use this approach to design approximation algorithms for the k-Forest problem, the k-Multicut problem, the k-Generalized connectivity problem, etc.

Keywords

k-Forest / k-Multicut / partial optimization / LP-rounding / Greedy algorithm / Approximation algorithm

References

[1] Agrawal A, Klein P, Ravi R. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 1995, 24(3): 440–456

[2] Goemans M, Williamson D. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 1995, 24(2): 296–317

[3] Garg N, Vazirani V, Yannakakis M. Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing, 1996, 25: 235–251

[4] Garg N, Vazirani V, Yannakakis M. Primal-dual approximation algorithm for integral flow and multicut in trees. Algorithmica, 1997, 18: 3–20

[5] Slavík P. Improved performance of the greedy algorithm for partial cover. Information Processing Letters, 1997, 64: 251–254

[6] Gupta A, Hajiaghayi M, Nagarajan V, Ravi R. Dial a ride from k-forest. ACM Transactions on Algorithms, 2010, 6(2): 41

[7] Hajiaghayi M, Jain K. The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. 2006, 631–640

[8] Segev D, Segev G. Approximate k-Steiner forests via the Lagrangian relaxation technique with internal preprocessing. In: Proceedings of the 14th Annual European Symposium on Algorithms. 2006, 600–611

[9] Zhang P, Xia M. An approximation algorithm to the k-Steiner forest problem. Theoretical Computer Science, 2009, 410(11): 1093–1098

[10] Zhang P, Zhu D, Luan J. An approximation algorithm for the generalized k-multicut problem. Discrete Applied Mathematics, 2012, 160(7–8): 1240–1247

[11] Golovin D, Nagarajan V, Singh M. Approximating the k-multicut prob lem. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 2006, 621–630

[12] Levin A, Segev D. Partial multicuts in trees. In: Proceedings of the 3rd Workshop on Approximation and Online Algorithms. 2005, 320–333

[13] Mestre J. Lagrangian relaxation and partial cover (extended abstract). In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science. 2008, 539–550

[14] Räcke H. Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 255–264

[15] Garg N. Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 2005, 302–309

[16] Johnson D. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 1974, 9: 256–278

[17] Lovász L. On the ratio of optimal inegral and factional covers. Discrete Mathematics, 1975, 13: 383–390

[18] Chvátal V. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 1979, 4: 233–235

[19] Bar-Yehuda R, Even S. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 1981, 2: 198–203

[20] Hochbaum D. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 1982, 11(3): 555–556

[21] Gandhi R, Khuller S, Srinivasan A. Approximation algorithms for partial covering problems. Journal of Algorithms, 2004, 53(1): 55–84

[22] Hochbaum D. The t-vertex cover problem: extending he half integrality framework with budget constraints. In: Proceedings of the 1st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 1998, 111–122

[23] Bshouty N, Burroughs L. Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Proceedings of the 15th Annual Symposium on the Theoretical Aspects of Computer Science. 1998, 298–308

[24] Bar-Yehuda R. Using homogeneous weights for approximating the partial cover problem. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. 1999, 71–75

[25] Garg N. A 3-approximation for the minimum tree spanning k-vertices. In: Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. 1996, 302–309

[26] Jain K, Vazirani V. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 2001, 48(2): 274–296

[27] Chudak F, Roughgarden T, Williamson D. Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Proramming, 2004, 100(2): 411–421

[28] Könemann J, Parekh O, Segev D. A unified approach to approximating partial covering problems. Algorithmica, 2011, 59(4): 489–509

[29] Gupta A, Kumar A. Greedy algorithms for Steiner forest. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing. 2015, 871–878

[30] Groß M, Gupta A, Kumar A, Matuschke J, Schmidt D, Schmidt M, Verschae J. A local-search algorithms for Steiner forest. In: Proceedings of the 9th Conference of Innovations in Theoretical Computer Science. 2018

[31] Bhaskara A, Charikar M, Chlamtac E, Feige U, Vijayaraghavan A. Detecting high log-densities: an O(n^1/4) approximation for densest ksubgraph. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing. 2010, 201–210

[32] Manurangsi P. Almost-polynomial ratio eth-hardness of approximating densest k-subgraph. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing. 2017, 954–961

[33] Segev D. Approximating k-generalized connectivity via collapsing HSTs. Journal of Combinatorial Optimization, 2011, 21: 364–382

[34] Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J. A general approach to online network optimization problems. ACM Transactions on Algorithms, 2006, 2(4): 640–660

[35] Chekuri C, Even G, Gupta A, Segev D. Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Transactions on Algorithms, 2011, 7(2): 18

[36] Gupta A. Improved results for directed multicut. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 2003, 454–455

[37] Agarwal A, Alon N, Charikar M. Improved approximation for directed cut problems. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 2007, 671–680

[38] Grandoni F, Rothvoß T. Network design via core detouring for problems without a core. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming. 2010, 490–502

[39] Chlebík M, Chlebíková J. The Steiner tree problem on graphs: inapproximability results. Theoretical Computer Science, 2008, 406: 207–214

[40] Chuzhoy J, Gupta A, Naor J, Sinha A. On the approximability of some network design problems. ACM Transactions on Algorithms, 2008, 4(2): 23:1–23:17

[41] Andrews M. Hardness of buy-at-bulk network design. In: Proceedings of the 45th Symposium on Foundations of Computer Science. 2004, 115–124

RIGHTS & PERMISSIONS

Higher Education Press