American Institute of Mathematical Sciences

Advanced
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

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, 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]

Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521
[2]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509
[3]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
[4]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[5]

Yan Huang. On Hausdorff dimension of the set of non-ergodic directions of two-genus double cover of tori. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2395-2409. doi: 10.3934/dcds.2018099
[6]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[7]

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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[8]

Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial & Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691
[9]

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 & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190
[10]

Stephen Thompson, Thomas I. Seidman. Approximation of a semigroup model of anomalous diffusion in a bounded set. Evolution Equations & Control Theory, 2013, 2 (1) : 173-192. doi: 10.3934/eect.2013.2.173
[11]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[12]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[13]

Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül. The set covering problem revisited: An empirical study of the value of dual information. Journal of Industrial & Management Optimization, 2015, 11 (2) : 575-594. doi: 10.3934/jimo.2015.11.575
[14]

Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008
[15]

Mostafa El Haffari, Ahmed Roubi. Prox-dual regularization algorithm for generalized fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1991-2013. doi: 10.3934/jimo.2017028
[16]

Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030
[17]

Shouchuan Hu, Xin Lu. Cover page and Preface. Conference Publications, 2015, 2015 (special) : i-i. doi: 10.3934/proc.2015.2015.si
[18]

Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417
[19]

David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429
[20]

Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences