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

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 and 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-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.

show all references

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.

[1]	Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521
[2]	Lican Kang, Yuan Luo, Jerry Zhijian Yang, Chang Zhu. A primal and dual active set algorithm for truncated $L_1$ regularized logistic regression. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022050
[3]	Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509
[4]	Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021134
[5]	Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems and Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
[6]	Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073
[7]	Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085
[8]	Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022031
[9]	Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[10]	Yan Huang. On Hausdorff dimension of the set of non-ergodic directions of two-genus double cover of tori. Discrete and Continuous Dynamical Systems, 2018, 38 (5) : 2395-2409. doi: 10.3934/dcds.2018099
[11]	Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[12]	Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021122
[13]	Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[14]	Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[15]	Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[16]	Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial and Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691
[17]	Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems and Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014
[18]	Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022008
[19]	Stephen Thompson, Thomas I. Seidman. Approximation of a semigroup model of anomalous diffusion in a bounded set. Evolution Equations and Control Theory, 2013, 2 (1) : 173-192. doi: 10.3934/eect.2013.2.173
[20]	I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Fengmin Wang Dachuan Xu Donglei Du Chenchen Wu
on Google Scholar
Fengmin Wang Dachuan Xu Donglei Du Chenchen Wu

[Back to Top]