-
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
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 |
References:
[1] |
E. Balas, The prize collecting traveling salesman problem,, Networks, 19 (1989), 621.
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.
doi: 10.1007/BF01581256. |
[3] |
E. Balas and M. Padberg, Set partitioning: a survey,, SIAM Review, 18 (1976), 710.
|
[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.
|
[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. |
[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. |
[7] |
J. Edmonds, Submodular functions, matroids, and certain polyhedra,, Combinatorial Structures and Their Applications, (1976), 69.
|
[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. |
[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. |
[10] |
S. Fujishige, Submodular Functions and Optimization,, 2nd edition, 58 (2005).
|
[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. |
[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. |
[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. |
[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. |
[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. |
[18] |
S. Iwata, A faster scaling algorithm for minimizing submodular functions,, SIAM Journal on Computing, 32 (2003), 833.
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.
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, (2009), 671.
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.
|
[22] |
R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R.E. Miller and J.W. Thatcher), (1972), 85.
|
[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. |
[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. |
[28] |
L. Lovász, Submodular functions and convexity,, in Mathematical Programming the State of the Art (eds. A. Bachem, (1983), 235.
|
[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. |
[30] |
M. W. Padberg, Covering, packing and knapsack problems,, Annals of Discrete Mathematics, 4 (1979), 265.
|
[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. |
[32] |
A. Schrijver, Combinatorial Optimization : Polyhedra and Efficiency,, Volume B, (2003), 39.
|
[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.
|
[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. |
[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. |
[3] |
E. Balas and M. Padberg, Set partitioning: a survey,, SIAM Review, 18 (1976), 710.
|
[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.
|
[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. |
[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. |
[7] |
J. Edmonds, Submodular functions, matroids, and certain polyhedra,, Combinatorial Structures and Their Applications, (1976), 69.
|
[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. |
[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. |
[10] |
S. Fujishige, Submodular Functions and Optimization,, 2nd edition, 58 (2005).
|
[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. |
[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. |
[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. |
[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. |
[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. |
[18] |
S. Iwata, A faster scaling algorithm for minimizing submodular functions,, SIAM Journal on Computing, 32 (2003), 833.
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.
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, (2009), 671.
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.
|
[22] |
R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R.E. Miller and J.W. Thatcher), (1972), 85.
|
[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. |
[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. |
[28] |
L. Lovász, Submodular functions and convexity,, in Mathematical Programming the State of the Art (eds. A. Bachem, (1983), 235.
|
[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. |
[30] |
M. W. Padberg, Covering, packing and knapsack problems,, Annals of Discrete Mathematics, 4 (1979), 265.
|
[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. |
[32] |
A. Schrijver, Combinatorial Optimization : Polyhedra and Efficiency,, Volume B, (2003), 39.
|
[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.
|
[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] |
Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020073 |
[5] |
Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020085 |
[6] |
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 |
[7] |
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 & Management Optimization, 2020 doi: 10.3934/jimo.2020056 |
[8] |
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 |
[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, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190 |
[10] |
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 |
[11] |
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 |
[12] |
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 |
[13] |
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 |
[14] |
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 |
[15] |
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 |
[16] |
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 |
[17] |
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 |
[18] |
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 |
[19] |
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 |
[20] |
Shouchuan Hu, Xin Lu. Cover page and Preface. Conference Publications, 2015, 2015 (special) : i-i. doi: 10.3934/proc.2015.2015.si |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]