Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties

Fengmin  Wang; Dachuan  Xu; Donglei  Du; Chenchen Wu

doi:10.3934/naco.2015.5.91

Article Contents

2015, Volume 5, Issue 2: 91-100. Doi: 10.3934/naco.2015.5.91

This issue Previous Article Preface Next Article Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term

Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties

1.
Department of Information and Operations Research, College of Applied Sciences, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124
2.
Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3
3.
College of Science, Tianjin University of Technology, Tianjin 300384

Received: October 2014

Revised: April 2015

Published: June 2015

Abstract / Introduction Related Papers Cited by

Abstract

We introduce two set cover problems with submodular costs and linear/submodular penalties and offer two approximation algorithms of ratios $\eta$ and $2\eta$ respectively via the primal-dual technique, where $\eta$ is the largest number of sets that each element belongs to.

Keywords:

Mathematics Subject Classification: Primary: 90C27; Secondary: 90C59.

Citation:

Related Papers

Cited by

References

[1]	E. Balas, The prize collecting traveling salesman problem, Networks, 19 (1989), 621-636.doi: 10.1002/net.3230190602.
[2]	D. Bienstock, M. Goemans, D. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem, Mathematical Programming, 59 (1993), 413-420.doi: 10.1007/BF01581256.
[3]	E. Balas and M. Padberg, Set partitioning: a survey, SIAM Review, 18 (1976), 710-760.
[4]	M. Charikar, S. Khuller, D. Mount and G. Narasimhan, Algorithms for facility location problems with outliers, in Symposium on Discrete Algorithms (SODA), SIAM, (2001), 642-651.
[5]	D. Du, R. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63 (2012), 191-200.doi: 10.1007/s00453-011-9526-1.
[6]	D. Du, R. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties, Algorithmica, 63 (2012), 191-200.doi: 10.1007/s00453-011-9526-1.
[7]	J. Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and Their Applications, (1976), 69-87.
[8]	U. Feige, A threshold of lnn for approximating set-cover, in 28th ACM Symposium on Theory of Computing, (1996), 314-318.doi: 10.1145/237814.237977.
[9]	L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization, Discrete Applied Mathematics, 131 (2003), 311-322.doi: 10.1016/S0166-218X(02)00458-4.
[10]	S. Fujishige, Submodular Functions and Optimization, 2nd edition, Elsevier, Amsterdam, the North-Holland, 58 (2005).
[11]	R. Gandhi, S. Khuller and A. Srinivasan, Approximation algorithms for partial covering problems, Journal of Algorithms, 53 (2004), 55-84.doi: 10.1016/j.jalgor.2004.04.002.
[12]	M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorical, (1981), 169-197.doi: 10.1007/BF02579273.
[13]	M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, Berlin, 1988.doi: 10.1007/978-3-642-97881-4.
[14]	R. S. Garfinkel and G. L. Nemhauser, Optimal set covering: a survey, Perspectives on Optimization, (1972), 164-183.
[15]	M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems, SIAM Journal on Computing, 24 (1995), 296-317.doi: 10.1137/S0097539793242618.
[16]	D. S. Hochbaum, Approximating covering and packing problems: set cover, vertex cover,independent set, and related problems, in Approximation Algorithms for NP-Hard Problems, chapter 3 (eds. D. S. Hochbaum), PWS Publishing Company, (1997), 94-143.
[17]	D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), 555-556.doi: 10.1137/0211045.
[18]	S. Iwata, A faster scaling algorithm for minimizing submodular functions, SIAM Journal on Computing, 32 (2003), 833-840.doi: 10.1137/S0097539701397813.
[19]	S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM, 48 (2001), 761-777.doi: 10.1145/502090.502096.
[20]	S. Iwata and K. Nagano, Submodular function minimization under covering constraints, in the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Atlanta, (2009), 671-680.doi: 10.1109/FOCS.2009.31.
[21]	S. Iwata and J. B. Orlin, A simple combinatorial algorithm for submodular function minimization, in the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, (2009), 1230-1237.
[22]	R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (eds. R.E. Miller and J.W. Thatcher), Plenum Press, (1972), 85-103.
[23]	A. Krause and C. Guestrin, Near-optimal observation selection using submodular functions, in the 22nd national conference on Artificial intelligence, AAAI, (2007), 1650-1654.
[24]	P. Kohli, P. Kumar and P. Torr, P³ beyond: move making algorithms for solving higher order functions, IEEE Transactions on Pattern Analysis and Machine Intelligence, 31 (2009), 1645-1656.
[25]	J. Könemann, O. Parekh and D. Segev, A unified approach to approximating partial covering problems, Algorithmica, 59 (2011), 489-509.doi: 10.1007/s00453-009-9317-0.
[26]	H. Lin and J. Bilmes, A class of submodular functions for document summarization, In: In North American chapter of the Association for Computational Linguistics/Human Language Technology Conference, (NAACL/HLT-2011), (2011).
[27]	Y. Li, D. Du, N. Xiu and D. Xu, Improved approximation algorithms for the facility location problems with linear/submodular penalty, in the 19th International Computing and Combinatorics Conference, 7936 (2013), 292-303.doi: 10.1007/978-3-642-38768-5_27.
[28]	L. Lovász, Submodular functions and convexity, in Mathematical Programming the State of the Art (eds. A. Bachem, M. Grtschel and B. Korte), Springer, (1983), 235-257.
[29]	J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization, Mathematical Programming, 118 (2009), 237-251.doi: 10.1007/s10107-007-0189-2.
[30]	M. W. Padberg, Covering, packing and knapsack problems, Annals of Discrete Mathematics, 4 (1979), 265-287.
[31]	A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Series B, 80 (2000), 346-355.doi: 10.1006/jctb.2000.1989.
[32]	A. Schrijver, Combinatorial Optimization : Polyhedra and Efficiency, Volume B, Part IV, Chapters 39-49, Springer, 2003.
[33]	R. Raz and S. Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability pep characterization of np, in the 29th Annual ACM Symposium on Theory of Computing, (1997), 475-484.
[34]	D. P. Williamson and D. B Shmoys, The Design of Approximation Algorithms, Cambridge University Press, New York, 2011.
[35]	D. Xu, F. Wang, D. Du and C. Wu, Primal-dual approximation algorithms for submodular vertex cover problems with linear/submodular penalties, in the 19th International Computing and Combinatorics Conference, 8591 (2014), 336-345.