# 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 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, P3 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, P3 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: