×

Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. (English) Zbl 1317.90260

Summary: 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.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Balas, The prize collecting traveling salesman problem,, Networks, 19, 621 (1989) · Zbl 0676.90089 · doi:10.1002/net.3230190602
[2] D. Bienstock, A note on the prize collecting traveling salesman problem,, Mathematical Programming, 59, 413 (1993) · Zbl 0793.90089 · doi:10.1007/BF01581256
[3] E. Balas, Set partitioning: a survey,, SIAM Review, 18, 710 (1976) · Zbl 0347.90064
[4] M. Charikar, Algorithms for facility location problems with outliers,, in Symposium on Discrete Algorithms (SODA), 642 (2001) · Zbl 1012.90026
[5] D. Du, A primal-dual approximation algorithm for the facility location problem with submodular penalties,, Algorithmica, 63, 191 (2012) · Zbl 1236.90066 · doi:10.1007/s00453-011-9526-1
[6] D. Du, A primal-dual approximation algorithm for the facility location problem with submodular penalties,, Algorithmica, 63, 191 (2012) · Zbl 1236.90066 · doi:10.1007/s00453-011-9526-1
[7] J. Edmonds, Submodular functions, matroids, and certain polyhedra,, Combinatorial Structures and Their Applications, 69 (1976)
[8] U. Feige, A threshold of lnn for approximating set-cover,, in 28th ACM Symposium on Theory of Computing, 314 (1996) · Zbl 0922.68067 · doi:10.1145/237814.237977
[9] L. Fleischer, A push-relabel framework for submodular function minimization and applications to parametric optimization,, Discrete Applied Mathematics, 131, 311 (2003) · Zbl 1030.90097 · doi:10.1016/S0166-218X(02)00458-4
[10] S. Fujishige, <em>Submodular Functions and Optimization</em>,, 2nd edition, 58 (2005) · Zbl 1119.90044
[11] R. Gandhi, Approximation algorithms for partial covering problems,, Journal of Algorithms, 53, 55 (2004) · Zbl 1068.68177 · doi:10.1016/j.jalgor.2004.04.002
[12] M. Grötschel, The ellipsoid method and its consequences in combinatorial optimization,, Combinatorical, 169 (1981) · Zbl 0492.90056 · doi:10.1007/BF02579273
[13] M. Grötschel, <em>Geometric Algorithms and Combinatorial Optimization</em>,, Springer-Verlag (1988) · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4
[14] R. S. Garfinkel, Optimal set covering: a survey,, Perspectives on Optimization, 164 (1972)
[15] M. X. Goemans, A general approximation technique for constrained forest problems,, SIAM Journal on Computing, 24, 296 (1995) · Zbl 0834.68055 · 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, 94 (1997)
[17] D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,, SIAM Journal on Computing, 11, 555 (1982) · Zbl 0486.68067 · doi:10.1137/0211045
[18] S. Iwata, A faster scaling algorithm for minimizing submodular functions,, SIAM Journal on Computing, 32, 833 (2003) · Zbl 1033.90106 · doi:10.1137/S0097539701397813
[19] S. Iwata, A combinatorial strongly polynomial algorithm for minimizing submodular functions,, Journal of the ACM, 48, 761 (2001) · Zbl 1127.90402 · doi:10.1145/502090.502096
[20] S. Iwata, Submodular function minimization under covering constraints,, in the 50th Annual IEEE Symposium on Foundations of Computer Science, 671 (2009) · Zbl 1292.68168 · doi:10.1109/FOCS.2009.31
[21] S. Iwata, A simple combinatorial algorithm for submodular function minimization,, in the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, 1230 (2009) · Zbl 1423.90226
[22] R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R.E. Miller and J.W. Thatcher), 85 (1972) · Zbl 0366.68041
[23] A. Krause, Near-optimal observation selection using submodular functions,, in the 22nd national conference on Artificial intelligence, 1650 (2007)
[24] P. Kohli, <I>P</I><SUP><I>3</I></SUP> beyond: move making algorithms for solving higher order functions,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 31, 1645 (2009)
[25] J. Könemann, A unified approach to approximating partial covering problems,, Algorithmica, 59, 489 (2011) · Zbl 1211.68511 · doi:10.1007/s00453-009-9317-0
[26] H. Lin, A class of submodular functions for document summarization,, In: In North American chapter of the Association for Computational Linguistics/Human Language Technology Conference (2011)
[27] Y. Li, Improved approximation algorithms for the facility location problems with linear/submodular penalty,, in the 19th International Computing and Combinatorics Conference, 7936, 292 (2013) · Zbl 1381.90053 · 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, 235 (1983) · Zbl 0566.90060
[29] J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization,, Mathematical Programming, 118, 237 (2009) · Zbl 1179.90290 · doi:10.1007/s10107-007-0189-2
[30] M. W. Padberg, Covering, packing and knapsack problems,, Annals of Discrete Mathematics, 4, 265 (1979) · Zbl 0407.90056
[31] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,, Journal of Combinatorial Theory, 80, 346 (2000) · Zbl 1052.90067 · doi:10.1006/jctb.2000.1989
[32] A. Schrijver, <em>Combinatorial Optimization : Polyhedra and Efficiency</em>,, Volume B, 39 (2003) · Zbl 1041.90001
[33] R. Raz, 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, 475 (1997) · Zbl 0963.68175
[34] D. P. Williamson, <em>The Design of Approximation Algorithms</em>,, Cambridge University Press (2011) · Zbl 1219.90004
[35] D. Xu, Primal-dual approximation algorithms for submodular vertex cover problems with linear/submodular penalties,, in the 19th International Computing and Combinatorics Conference, 8591, 336 (2014) · Zbl 1338.90481
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.