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

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

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

Fengmin Wang ^1, , Dachuan Xu ^1, , Donglei Du ^2, and Chenchen Wu ^3,

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

Abstract
Related Papers

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: primal-dual., penalties, submodular cost, Set cover, approximation algorithm.

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

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, P³ 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, P³ 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:

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

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

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors