Citation: |
[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. |