Citation: |
[1] |
U. Aickelin, An indirect genetic algorithm for set covering problems, Journal of the Operations Research, 53 (2002), 1118-1126.doi: 10.1057/palgrave.jors.2601317. |
[2] |
Z. N. Azimi, P. Toth and L. Galli, An electromagnetism metaheuristic for the unicost set covering problem, European Journal of Operational Research, 205 (2010), 290-300.doi: 10.1016/j.ejor.2010.01.035. |
[3] |
E. Balas and M. C. Carrera, A dynamic subgradient-based branch-and-bound procedure for set covering, Operations Research, 44 (1996), 875-890.doi: 10.1287/opre.44.6.875. |
[4] |
R. Bar-Yehuda and S. Even, A linear-time approximation algorithm for the weighted vertex cover problem, Journal of Algorithms, 2 (1981), 198-203.doi: 10.1016/0196-6774(81)90020-1. |
[5] |
R. Bar-Yehuda and S. Even, On approximating a vertex cover for planar graphs, in 14th ACM Symposium on Theory of Computing, San Francisco, California, (1982), 303-309.doi: 10.1145/800070.802205. |
[6] |
R. Bar-Yehuda and D. Rawitz, On the equivalence between the primal-dual schema and the local ratio technique, SIAM Journal on Discrete Mathematics, 19 (2005), 762-797.doi: 10.1137/050625382. |
[7] |
J. E. Beasley, An algorithm for set covering problem, European Journal of Operational Research, 31 (1987), 85-93.doi: 10.1016/0377-2217(87)90141-X. |
[8] |
J. E. Beasley, A Lagrangian heuristic for set covering problems, Naval Research Logistics, 37 (1990), 151-164.doi: 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO;2-2. |
[9] |
J. E. Beasley and P. C. Chu, A genetic algorithm for the set covering problem, European Journal of Operational Research, 94 (1996), 392-404.doi: 10.1016/0377-2217(95)00159-X. |
[10] |
J. E. Beasley and K. Jornsten, Enhancing an algorithm for set covering problems, European Journal of Operational Research, 58 (1992), 293-300.doi: 10.1016/0377-2217(92)90215-U. |
[11] |
D. Bertsimas and R. Vohra, Rounding algorithms for covering problems, Mathematical Programming, 80 (1998), 63-89.doi: 10.1007/BF01582131. |
[12] |
H. Brönnimann and M. Goodrich, Almost optimal set covers in finite vc-dimension, Discrete and Computational Geometry, 14 (1995), 463-479.doi: 10.1007/BF02570718. |
[13] |
M. J. Brusco, L. W. Jacobs and G. M. Thompson, A morphing procedure to supplement a simulated annealing heuristic for cost- and coverage-correlated set-covering problems, Annals of Operations Research, 86 (1999), 611-627.doi: 10.1023/A:1018900128545. |
[14] |
A. Caprara, M. Fischetti and P. Toth, A heuristic method for the set covering problem, Operations Research, 47 (1999), 730-743.doi: 10.1287/opre.47.5.730. |
[15] |
A. Caprara, P. Toth and M. Fischetti, Algorithms for the set covering problem, Annals of Operations Research, 98 (2000), 353-371.doi: 10.1023/A:1019225027893. |
[16] |
M. Caserta, Metaheuristics: Progress in Complex Systems Optimization, 43-63, Springer, Berlin, 2007. |
[17] |
S. Ceria, P. Nobili and A. Sassano, A Lagrangian-based heuristic for large-scale set covering problems, Mathematical Programmimg, 81 (1998), 215-228.doi: 10.1007/BF01581106. |
[18] |
V. Chvatal, A greedy-heuristic for the set covering problem, Mathematics of Operations Research, 4 (1979), 233-235.doi: 10.1287/moor.4.3.233. |
[19] |
G. Even, D. Rawitz and S. Shahar, Hitting sets when the vc-dimension is small, Information Processing Letters, 95 (2005), 358-362.doi: 10.1016/j.ipl.2005.03.010. |
[20] |
T. A. Feo and M. Resende, A probabilistic heuristic for a computationally difficult set covering problem, Operations Research Letters, 8 (1989), 67-71.doi: 10.1016/0167-6377(89)90002-3. |
[21] |
M. Finger, T. Stützle and H. Lourenço, Exploiting fitness distance correlation of set covering problems, Lecture Notes in Computer Science, 2279 (2002), 61-71.doi: 10.1007/3-540-46004-7_7. |
[22] |
M. L. Fisher and P. Kedia, Optimal solution of set covering/partitioning problems using dual heuristics, Management Science, 36 (1990), 674-688.doi: 10.1287/mnsc.36.6.674. |
[23] |
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. |
[24] |
F. C. Gomes, C. N. Meneses, P. M. Pardalos and G. V. R. Viana, Experimental analysis of approximation algorithms for the vertex cover and set covering problems, Computers & Operations Research, 33 (2006), 3520-3534.doi: 10.1016/j.cor.2005.03.030. |
[25] |
T. Grossman and A. Wool, Computational experience with aproximation algorithms for the set covering problem, European Journal of Operational Research, 101 (1997), 81-92.doi: 10.1016/S0377-2217(96)00161-0. |
[26] |
N. Hall and R. V. Vohra, Pareto optimality and a class of set covering heuristics, Annals of Operations Research, 43 (1993), 279-284.doi: 10.1007/BF02025298. |
[27] |
M. Haouari and J. S. Chaouachi, A probabilistic greedy search algorithm for combinatorial optimization with application to the set covering problem, Journal of the Operational Research Society, 53 (2002), 792-799. |
[28] |
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. |
[29] |
IBM, 2013, IBM ILOG CPLEX Optimizer performance benchmarks. |
[30] |
L. W. Jacobs and M. J. Brusco, A local search heuristic for large set-covering problems, Naval Research Logistics, 42 (1995), 1129-1140.doi: 10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M. |
[31] |
G. Kinney, J. W. Barnes and B. Colleti, A Group Theoretic Tabu Search Algorithm for Set Covering Problems, Technical report, Graduate Program in Operations Research and Industrial Engineering, The University of Texas, Austin, Texas 78712, 2004. |
[32] |
G. Lan, G. W. DePuy and G. E. Whitehouse, An effective and simple heuristic for the set covering problem, European Journal of Operational Research, 176 (2007), 1387-1403.doi: 10.1016/j.ejor.2005.09.028. |
[33] |
L. A. N. Lorena and L. S. Lopes, Genetic algorithms applied to computationally difficult set covering problems, Journal of Operational Research Society, 48 (1997), 440-445. |
[34] |
C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of ACM, 41 (1994), 960-981.doi: 10.1145/185675.306789. |
[35] |
E. Marchiori and A. Steenbeek, An iterated heuristic algorithm for the set covering problem, in Proceedings WAE'98 Saarbrücken, (1998), 1-3. |
[36] |
V. Melkonian, New primal-dual algorithms for steiner tree problems, Computers & Operations Research, 34 (2007), 2147-2167.doi: 10.1016/j.cor.2005.08.009. |
[37] |
N. Musliu, Local search algorithm for unicost set covering problem, Lecture Notes in Artificial Intelligence, 4031 (2006), 302-311.doi: 10.1007/11779568_34. |
[38] |
I. Muter, S. I. Birbil and G. Sahin, Combination of metaheuristic and exact algorithms for solving set covering-type optimization problems, INFORMS Journal on Computing, 22 (2010), 603-619.doi: 10.1287/ijoc.1090.0376. |
[39] |
C. A. Oliveira and P. M. Pardalos, A survey of combinatorial optimization problems in multicast routing, Computers & Operations Research, 32 (2005), 1953-1981, URL http://www.sciencedirect.com/science/article/pii/S0305054803003873.doi: 10.1016/j.cor.2003.12.007. |
[40] |
OR-lib, 2013, http://people.brunel.ac.uk/~ mastjjb/jeb/info.html. |
[41] |
Z. G. Ren, Z. R. Feng, L. J. Ke and Z. J. Zhang, New ideas for applying ant colony optimization to the set covering problem, Computers & Industrial Engineering, 58 (2010), 774-784.doi: 10.1016/j.cie.2010.02.011. |
[42] |
R. A. Rushmeier and G. L. Nemhauser, Experiments with parallel branch-and-bound algorithms for the set covering problem, Operations Research Letters, 13 (1993), 277-285.doi: 10.1016/0167-6377(93)90050-Q. |
[43] |
S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem, Journal of the Operations Research Society of Japan, 50 (2007), 350-375. |
[44] |
V. Vapnik, Statistical Learning Theory, Wiley-Interscience, 1998. |
[45] |
F. J. Vasko and G. R. Wilson, An efficient heuristic for large set covering problems, Naval Research Logistics Quarterly, 31 (1984), 163-171.doi: 10.1002/nav.3800310118. |
[46] |
V. V. Vazirani, Theoretical aspects of computer science, Springer, Verlag LNCS, 2292 (2002), 198-207.doi: 10.1007/3-540-45878-6_7. |
[47] |
D. P. Williamson, The primal-dual method for approximation algorithms, Mathematical Programming, 91 (2002), 447-478.doi: 10.1007/s101070100262. |
[48] |
M. Yagiura, M. Kishida and T. Ibaraki, A 3-flip neighborhood local search for the set covering problem, European Journal of Operational Research, 172 (2006), 472-499.doi: 10.1016/j.ejor.2004.10.018. |
[49] |
B. Yelbay, Primal-dual Heuristics for Solving the Set Covering Problem, Master's thesis, Sabanci University, Istanbul,Turkey, 2010. |
[50] |
B. Yelbay, S. I. Birbil, K. Bülbül and H. Jamil, Trade-offs computing minimum hub cover toward optimized graph query processing, 2013, http://arxiv.org/abs/1311.1626. |