# American Institute of Mathematical Sciences

2015, 5(2): 91-100. doi: 10.3934/naco.2015.5.91

## 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, China, China 2 Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3, Canada 3 College of Science, Tianjin University of Technology, Tianjin 300384

Received  October 2014 Revised  April 2015 Published  June 2015

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.
Citation: Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91
##### References:
 [1] E. Balas, The prize collecting traveling salesman problem,, Networks, 19 (1989), 621.  doi: 10.1002/net.3230190602.  Google Scholar [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.  doi: 10.1007/BF01581256.  Google Scholar [3] E. Balas and M. Padberg, Set partitioning: a survey,, SIAM Review, 18 (1976), 710.   Google Scholar [4] M. Charikar, S. Khuller, D. Mount and G. Narasimhan, Algorithms for facility location problems with outliers,, in Symposium on Discrete Algorithms (SODA), (2001), 642.   Google Scholar [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.  doi: 10.1007/s00453-011-9526-1.  Google Scholar [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.  doi: 10.1007/s00453-011-9526-1.  Google Scholar [7] J. Edmonds, Submodular functions, matroids, and certain polyhedra,, Combinatorial Structures and Their Applications, (1976), 69.   Google Scholar [8] U. Feige, A threshold of lnn for approximating set-cover,, in 28th ACM Symposium on Theory of Computing, (1996), 314.  doi: 10.1145/237814.237977.  Google Scholar [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.  doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar [10] S. Fujishige, Submodular Functions and Optimization,, 2nd edition, 58 (2005).   Google Scholar [11] R. Gandhi, S. Khuller and A. Srinivasan, Approximation algorithms for partial covering problems,, Journal of Algorithms, 53 (2004), 55.  doi: 10.1016/j.jalgor.2004.04.002.  Google Scholar [12] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,, Combinatorical, (1981), 169.  doi: 10.1007/BF02579273.  Google Scholar [13] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization,, Springer-Verlag, (1988).  doi: 10.1007/978-3-642-97881-4.  Google Scholar [14] R. S. Garfinkel and G. L. Nemhauser, Optimal set covering: a survey,, Perspectives on Optimization, (1972), 164.   Google Scholar [15] M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems,, SIAM Journal on Computing, 24 (1995), 296.  doi: 10.1137/S0097539793242618.  Google Scholar [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, (1997), 94.   Google Scholar [17] D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,, SIAM Journal on Computing, 11 (1982), 555.  doi: 10.1137/0211045.  Google Scholar [18] S. Iwata, A faster scaling algorithm for minimizing submodular functions,, SIAM Journal on Computing, 32 (2003), 833.  doi: 10.1137/S0097539701397813.  Google Scholar [19] S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,, Journal of the ACM, 48 (2001), 761.  doi: 10.1145/502090.502096.  Google Scholar [20] S. Iwata and K. Nagano, Submodular function minimization under covering constraints,, in the 50th Annual IEEE Symposium on Foundations of Computer Science, (2009), 671.  doi: 10.1109/FOCS.2009.31.  Google Scholar [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.   Google Scholar [22] R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R.E. Miller and J.W. Thatcher), (1972), 85.   Google Scholar [23] A. Krause and C. Guestrin, Near-optimal observation selection using submodular functions,, in the 22nd national conference on Artificial intelligence, (2007), 1650.   Google Scholar [24] P. Kohli, P. Kumar and P. Torr, P3 beyond: move making algorithms for solving higher order functions,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 31 (2009), 1645.   Google Scholar [25] J. Könemann, O. Parekh and D. Segev, A unified approach to approximating partial covering problems,, Algorithmica, 59 (2011), 489.  doi: 10.1007/s00453-009-9317-0.  Google Scholar [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, (2011).   Google Scholar [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.  doi: 10.1007/978-3-642-38768-5_27.  Google Scholar [28] L. Lovász, Submodular functions and convexity,, in Mathematical Programming the State of the Art (eds. A. Bachem, (1983), 235.   Google Scholar [29] J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization,, Mathematical Programming, 118 (2009), 237.  doi: 10.1007/s10107-007-0189-2.  Google Scholar [30] M. W. Padberg, Covering, packing and knapsack problems,, Annals of Discrete Mathematics, 4 (1979), 265.   Google Scholar [31] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,, Journal of Combinatorial Theory, 80 (2000), 346.  doi: 10.1006/jctb.2000.1989.  Google Scholar [32] A. Schrijver, Combinatorial Optimization : Polyhedra and Efficiency,, Volume B, (2003), 39.   Google Scholar [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.   Google Scholar [34] D. P. Williamson and D. B Shmoys, The Design of Approximation Algorithms,, Cambridge University Press, (2011).   Google Scholar [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.   Google Scholar

show all references

##### References:
 [1] E. Balas, The prize collecting traveling salesman problem,, Networks, 19 (1989), 621.  doi: 10.1002/net.3230190602.  Google Scholar [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.  doi: 10.1007/BF01581256.  Google Scholar [3] E. Balas and M. Padberg, Set partitioning: a survey,, SIAM Review, 18 (1976), 710.   Google Scholar [4] M. Charikar, S. Khuller, D. Mount and G. Narasimhan, Algorithms for facility location problems with outliers,, in Symposium on Discrete Algorithms (SODA), (2001), 642.   Google Scholar [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.  doi: 10.1007/s00453-011-9526-1.  Google Scholar [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.  doi: 10.1007/s00453-011-9526-1.  Google Scholar [7] J. Edmonds, Submodular functions, matroids, and certain polyhedra,, Combinatorial Structures and Their Applications, (1976), 69.   Google Scholar [8] U. Feige, A threshold of lnn for approximating set-cover,, in 28th ACM Symposium on Theory of Computing, (1996), 314.  doi: 10.1145/237814.237977.  Google Scholar [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.  doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar [10] S. Fujishige, Submodular Functions and Optimization,, 2nd edition, 58 (2005).   Google Scholar [11] R. Gandhi, S. Khuller and A. Srinivasan, Approximation algorithms for partial covering problems,, Journal of Algorithms, 53 (2004), 55.  doi: 10.1016/j.jalgor.2004.04.002.  Google Scholar [12] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,, Combinatorical, (1981), 169.  doi: 10.1007/BF02579273.  Google Scholar [13] M. Grötschel, L. Lovász and A. Schrijver, Geometric Algorithms and Combinatorial Optimization,, Springer-Verlag, (1988).  doi: 10.1007/978-3-642-97881-4.  Google Scholar [14] R. S. Garfinkel and G. L. Nemhauser, Optimal set covering: a survey,, Perspectives on Optimization, (1972), 164.   Google Scholar [15] M. X. Goemans and D. P. Williamson, A general approximation technique for constrained forest problems,, SIAM Journal on Computing, 24 (1995), 296.  doi: 10.1137/S0097539793242618.  Google Scholar [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, (1997), 94.   Google Scholar [17] D. S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,, SIAM Journal on Computing, 11 (1982), 555.  doi: 10.1137/0211045.  Google Scholar [18] S. Iwata, A faster scaling algorithm for minimizing submodular functions,, SIAM Journal on Computing, 32 (2003), 833.  doi: 10.1137/S0097539701397813.  Google Scholar [19] S. Iwata, L. Fleischer and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,, Journal of the ACM, 48 (2001), 761.  doi: 10.1145/502090.502096.  Google Scholar [20] S. Iwata and K. Nagano, Submodular function minimization under covering constraints,, in the 50th Annual IEEE Symposium on Foundations of Computer Science, (2009), 671.  doi: 10.1109/FOCS.2009.31.  Google Scholar [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.   Google Scholar [22] R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R.E. Miller and J.W. Thatcher), (1972), 85.   Google Scholar [23] A. Krause and C. Guestrin, Near-optimal observation selection using submodular functions,, in the 22nd national conference on Artificial intelligence, (2007), 1650.   Google Scholar [24] P. Kohli, P. Kumar and P. Torr, P3 beyond: move making algorithms for solving higher order functions,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 31 (2009), 1645.   Google Scholar [25] J. Könemann, O. Parekh and D. Segev, A unified approach to approximating partial covering problems,, Algorithmica, 59 (2011), 489.  doi: 10.1007/s00453-009-9317-0.  Google Scholar [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, (2011).   Google Scholar [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.  doi: 10.1007/978-3-642-38768-5_27.  Google Scholar [28] L. Lovász, Submodular functions and convexity,, in Mathematical Programming the State of the Art (eds. A. Bachem, (1983), 235.   Google Scholar [29] J. B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization,, Mathematical Programming, 118 (2009), 237.  doi: 10.1007/s10107-007-0189-2.  Google Scholar [30] M. W. Padberg, Covering, packing and knapsack problems,, Annals of Discrete Mathematics, 4 (1979), 265.   Google Scholar [31] A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time,, Journal of Combinatorial Theory, 80 (2000), 346.  doi: 10.1006/jctb.2000.1989.  Google Scholar [32] A. Schrijver, Combinatorial Optimization : Polyhedra and Efficiency,, Volume B, (2003), 39.   Google Scholar [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.   Google Scholar [34] D. P. Williamson and D. B Shmoys, The Design of Approximation Algorithms,, Cambridge University Press, (2011).   Google Scholar [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.   Google Scholar
 [1] Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001 [2] Xi Zhao, Teng Niu. Impacts of horizontal mergers on dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020173 [3] Ferenc Weisz. Dual spaces of mixed-norm martingale hardy spaces. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020285 [4] Bo Tan, Qinglong Zhou. Approximation properties of Lüroth expansions. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020389 [5] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [6] Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043 [7] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [8] Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463 [9] Bilal Al Taki, Khawla Msheik, Jacques Sainte-Marie. On the rigid-lid approximation of shallow water Bingham. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 875-905. doi: 10.3934/dcdsb.2020146 [10] P. K. Jha, R. Lipton. Finite element approximation of nonlocal dynamic fracture models. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1675-1710. doi: 10.3934/dcdsb.2020178 [11] Simone Fagioli, Emanuela Radici. Opinion formation systems via deterministic particles approximation. Kinetic & Related Models, 2021, 14 (1) : 45-76. doi: 10.3934/krm.2020048 [12] Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169 [13] Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15 (2) : 365-386. doi: 10.3934/amc.2020071 [14] Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167 [15] Hongxia Sun, Yao Wan, Yu Li, Linlin Zhang, Zhen Zhou. Competition in a dual-channel supply chain considering duopolistic retailers with different behaviours. Journal of Industrial & Management Optimization, 2021, 17 (2) : 601-631. doi: 10.3934/jimo.2019125 [16] Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158 [17] Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322 [18] Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168 [19] Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 [20] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

Impact Factor:

## Metrics

• PDF downloads (75)
• HTML views (0)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]