Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties

详细信息    查看全文

• 作者：Dachuan Xu (18)
  Fengmin Wang (18)
  Donglei Du (19)
  Chenchen Wu (18)
  
• 关键词：Primal ; dual ; Approximation algorithm ; Submodular function ; Vertex cover problem
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8591
• 期：1
• 页码：336-345
• 全文大小：195 KB
• 参考文献：1. Bshouty, N., Burroughs, L.: Massaging a Linear Programming Solution to Give a 2-Approximation for a Generalization of the Vertex Cover Problem. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.聽1373, pp. 298鈥?08. Springer, Heidelberg (1998) CrossRef
  2. Bar-Yehuda, R., Even, S.: A Linear-Time Approximation Algorithm for the Weighted Vertex Cover. J. Algorithms聽2, 198鈥?03 (1981) CrossRef
  3. Bar-Yehuda, R., Even, S.: A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem. Ann. Discrete Math.聽25, 27鈥?6 (1985)
  4. Bar-Yehuda, R., Hermelin, D., Rawitz, D.: An Extension of the Nemhauser-Trotter Theorem to Generalized Vertex Cover with Applications. SIAM J. Discrete Math.聽24, 287鈥?00 (2010) CrossRef
  5. Bar-Yehuda, R., Rawitz, D.: On the Equivalence between the Primal-Dual Schema and the Local Technique. SIAM J. Discrete Math.聽19, 762鈥?97 (2005) CrossRef
  6. Bienstock, D., Goemans, M., Simchi-Levi, D., Williamson, D.: A Note on the Prize Collecting Traveling Salesman Problem. Math. Program.聽59, 413鈥?20 (1993) CrossRef
  7. Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Algorithms for Facility Location Problems with Outliers. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642鈥?51. SIAM Press, Washington SC (2001)
  8. Du, D., Lu, R., Xu, D.: A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties. Algorithmica聽63, 191鈥?00 (2012) CrossRef
  9. Edmonds, J.: Submodular Functions, Matroids, and Certain Polyhedra. In: Guy, R., Hanam, H., Sauer, N., Schonheim, J. (eds.) Combinatorial Structures and Their Applications (Proc. 1969 Calgary Conference), pp. 69鈥?7. Gordon and Breach, New York (1970)
  10. Fleischer, L., Iwata, S.: A Push-Relabel Framework for Submodular Function Minimization and Applications to Parametric Optimization. Discrete Appl. Math.聽131, 311鈥?22 (2003) CrossRef
  11. Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)
  12. Guha, S., Hassin, R., Khuller, S., Or, E.: Capacitated Vertex Covering. J. Algorithms聽48, 257鈥?70 (2003) CrossRef
  13. Gr枚tschel, M., Lov谩sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988) CrossRef
  14. Goemans, M.X., Williamson, D.P.: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput.聽24, 296鈥?17 (1995) CrossRef
  15. Halperin, E.: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs. SIAM J. Comput.聽31, 1608鈥?623 (2002) CrossRef
  16. Hochbaum, D.S.: Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J. Comput.聽11, 555鈥?56 (1982) CrossRef
  17. Hochbaum, D.S.: Approximation Algorithms for NP-hard Problems. PWS Publishing Company, Boston (1997)
  18. Hochbaum, D.S.: Solving Integer Programs over Monotone Inequalities in Three Variables: a Framework of Half Integrality and Good Approximations. Eur. J. Oper. Res.聽140, 291鈥?21 (2002) CrossRef
  19. Iwata, S., Fleischer, L., Fujishige, S.: A Combinatorial Strongly Polynomial Algorithm for Minimizing Submodular Functions. J. ACM聽48, 761鈥?77 (2001) CrossRef
  20. Iwata, S., Nagano, K.: Submodular Function Minimization under Covering Constraints. In: 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 671鈥?80. IEEE Press, Atlanta (2009)
  21. Karakostas, G.: A Better Approximation Ratio for the Vertex Cover Problem. ACM Trans. on Algorithms 5, Article No. 41 (2009)
  22. Khot, S., Regev, O.: Vertex Cover Might Be Hard to Approxmate to with 2鈥夆垝鈥?em class="a-plus-plus">蔚. J. Comput. Syst. Sci.聽74, 335鈥?49 (2008) CrossRef
  23. Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85鈥?03. Springer, US (1972)
  24. Li, Y., Du, D., Xiu, N., Xu, D.: Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.聽7936, pp. 292鈥?03. Springer, Heidelberg (2013) CrossRef
  25. Lov谩sz, L.: Submodular Functions and Convexity. In: Bachem, A., Grtschel, M., Korte, B. (eds.) Mathematical Programming The State of the Art, pp. 235鈥?57. Springer, Heidelberg (1983) CrossRef
  26. Schrijver, A.: A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time. J. Comb. Theory B聽80, 346鈥?55 (2000) CrossRef
  
• 作者单位：Dachuan Xu (18)
  Fengmin Wang (18)
  Donglei Du (19)
  Chenchen Wu (18)
  
  18. College of Science, Tianjin University of Technology, Tianjin, 300384, China
  19. Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3, Canada
  
• ISSN：1611-3349

文摘

In this paper, we introduce two variants of the submodular vertex cover problem, namely, the submodular vertex cover problems with linear and submodular penalties, for which we present two primal-dual approximation algorithms with approximation ratios of 2 and 4, respectively. Implementing the primal-dual framework directly on the dual programs of the linear program relaxations for these two variants cannot guarantee the dual ascending process terminates in polynomial time. To overcome this difficulty, we relax the two dual programs to slightly weaker versions which lead to two primal-dual approximation algorithms with the aforeclaimed approximation ratios.