The LP-rounding plus greed approach for partial optimization revisited

doi:10.1007/s11704-020-0368-3

Frontiers of Computer Science

2022, Vol. 16

Issue (1): 161402 https://doi.org/10.1007/s11704-020-0368-3

本期目录

The LP-rounding plus greed approach for partial optimization revisited

Peng ZHANG(

)

School of Software, Shandong University, Jinan 250101, China

全文: PDF(140 KB)

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.

Key words： k-Forest k-Multicut partial optimization LP-rounding Greedy algorithm Approximation algorithm

收稿日期: 2020-07-21 出版日期: 2021-09-28

Corresponding Author(s): Peng ZHANG

引用本文:

. [J]. Frontiers of Computer Science, 2022, 16(1): 161402.
Peng ZHANG. The LP-rounding plus greed approach for partial optimization revisited. Front. Comput. Sci., 2022, 16(1): 161402.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-020-0368-3
https://academic.hep.com.cn/fcs/CN/Y2022/V16/I1/161402

1	A Agrawal, P Klein, R Ravi. When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 1995, 24(3): 440–456 https://doi.org/10.1137/S0097539792236237
2	M Goemans, D Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 1995, 24(2): 296–317 https://doi.org/10.1137/S0097539793242618
3	N Garg, V Vazirani, M Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing, 1996, 25: 235–251 https://doi.org/10.1137/S0097539793243016
4	N Garg, V Vazirani, M Yannakakis. Primal-dual approximation algorithm for integral flow and multicut in trees. Algorithmica, 1997, 18: 3–20 https://doi.org/10.1007/BF02523685
5	P Slavík. Improved performance of the greedy algorithm for partial cover. Information Processing Letters, 1997, 64: 251–254 https://doi.org/10.1016/S0020-0190(97)00182-8
6	A Gupta, M Hajiaghayi, V Nagarajan, R Ravi. Dial a ride from k-forest. ACM Transactions on Algorithms, 2010, 6(2): 41 https://doi.org/10.1145/1721837.1721857
7	M Hajiaghayi, K Jain. 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 https://doi.org/10.1145/1109557.1109626
8	D Segev, G Segev. 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 https://doi.org/10.1007/11841036_54
9	P Zhang, M Xia. An approximation algorithm to the k-Steiner forest problem. Theoretical Computer Science, 2009, 410(11): 1093–1098 https://doi.org/10.1016/j.tcs.2008.10.033
10	P Zhang, D Zhu, J Luan. An approximation algorithm for the generalized k-multicut problem. Discrete Applied Mathematics, 2012, 160(7–8): 1240–1247 https://doi.org/10.1016/j.dam.2012.01.016
11	D Golovin, V Nagarajan, M Singh. Approximating the k-multicut prob lem. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms. 2006, 621–630 https://doi.org/10.1145/1109557.1109625
12	A Levin, D Segev. Partial multicuts in trees. In: Proceedings of the 3rd Workshop on Approximation and Online Algorithms. 2005, 320–333 https://doi.org/10.1007/11671411_25
13	J Mestre. Lagrangian relaxation and partial cover (extended abstract). In: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science. 2008, 539–550
14	H Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 255–264 https://doi.org/10.1145/1374376.1374415
15	N Garg. 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 https://doi.org/10.1145/1060590.1060650
16	D Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 1974, 9: 256–278 https://doi.org/10.1016/S0022-0000(74)80044-9
17	L Lovász. On the ratio of optimal inegral and factional covers. Discrete Mathematics, 1975, 13: 383–390 https://doi.org/10.1016/0012-365X(75)90058-8
18	V Chvátal. A greedy heuristic for the set covering problem. Mathematics of Operations Research, 1979, 4: 233–235 https://doi.org/10.1287/moor.4.3.233
19	R Bar-Yehuda, S Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 1981, 2: 198–203 https://doi.org/10.1016/0196-6774(81)90020-1
20	D Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 1982, 11(3): 555–556 https://doi.org/10.1137/0211045
21	R Gandhi, S Khuller, A Srinivasan. Approximation algorithms for partial covering problems. Journal of Algorithms, 2004, 53(1): 55–84 https://doi.org/10.1016/j.jalgor.2004.04.002
22	D Hochbaum. 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 https://doi.org/10.1007/BFb0053968
23	N Bshouty, L Burroughs. 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 https://doi.org/10.1007/BFb0028569
24	R Bar-Yehuda. Using homogeneous weights for approximating the partial cover problem. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms. 1999, 71–75
25	N Garg. 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	K Jain, V Vazirani. 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 https://doi.org/10.1145/375827.375845
27	F Chudak, T Roughgarden, D Williamson. Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Proramming, 2004, 100(2): 411–421 https://doi.org/10.1007/s10107-003-0479-2
28	J Könemann, O Parekh, D Segev. A unified approach to approximating partial covering problems. Algorithmica, 2011, 59(4): 489–509 https://doi.org/10.1007/s00453-009-9317-0
29	A Gupta, A Kumar. Greedy algorithms for Steiner forest. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing. 2015, 871–878 https://doi.org/10.1145/2746539.2746590
30	M Groß, A Gupta, A Kumar, J Matuschke, D Schmidt, M Schmidt, J Verschae. A local-search algorithms for Steiner forest. In: Proceedings of the 9th Conference of Innovations in Theoretical Computer Science. 2018
31	A Bhaskara, M Charikar, E Chlamtac, U Feige, A Vijayaraghavan. Detecting high log-densities: an O(n1/4) approximation for densest ksubgraph. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing. 2010, 201–210 https://doi.org/10.1145/1806689.1806719
32	P Manurangsi. 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 https://doi.org/10.1145/3055399.3055412
33	D Segev. Approximating k-generalized connectivity via collapsing HSTs. Journal of Combinatorial Optimization, 2011, 21: 364–382 https://doi.org/10.1007/s10878-009-9256-3
34	N Alon, B Awerbuch, Y Azar, N Buchbinder, J Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms, 2006, 2(4): 640–660 https://doi.org/10.1145/1198513.1198522
35	C Chekuri, G Even, A Gupta, D Segev. Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Transactions on Algorithms, 2011, 7(2): 18 https://doi.org/10.1145/1921659.1921664
36	A Gupta. Improved results for directed multicut. In: Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. 2003, 454–455
37	A Agarwal, N Alon, M Charikar. Improved approximation for directed cut problems. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. 2007, 671–680 https://doi.org/10.1145/1250790.1250888
38	F Grandoni, T Rothvoß. 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 https://doi.org/10.1007/978-3-642-14165-2_42
39	M Chlebík, J Chlebíková. The Steiner tree problem on graphs: inapproximability results. Theoretical Computer Science, 2008, 406: 207–214 https://doi.org/10.1016/j.tcs.2008.06.046
40	J Chuzhoy, A Gupta, J Naor, A Sinha. On the approximability of some network design problems. ACM Transactions on Algorithms, 2008, 4(2): 23:1–23:17 https://doi.org/10.1145/1361192.1361200
41	M Andrews. Hardness of buy-at-bulk network design. In: Proceedings of the 45th Symposium on Foundations of Computer Science. 2004, 115–124

[1]

Highlights

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed