Efficient network algorithms for two special cases of the weighted set cover problem

References

• Ahuja, R. K., Magnanti, T. L., & Orlin, J. B., 1993. Network Flows. Englewood Cliffs, NJ: Prentice Hall.
   Google Scholar
• Bilal, N., Galinier, P., & Guibault, F. (2014). An iterated-tabu-search heuristic for a variant of the partial set covering problem. Journal of Heuristics, 20(2), 143–164.10.1007/s10732-013-9235-9
   Web of Science ®Google Scholar
• Bruni, R., & Montanari, U. (2017). Partial orders and fixpoints. Models of Computation (pp. 103–126). Cham: Springer International Publishing.10.1007/978-3-319-42900-7
   Google Scholar
• Crawford, B., Soto, R., & Monfroy, E., 2013. Cultural algorithms for the set covering problem. Cham: Springer International Publishing.
   Google Scholar
• Crawford, B., Soto, R., Cuesta, R., & Paredes, F. (2014a). Application of the artificial bee colony algorithm for solving the set covering problem. The Scientific World Journal, 2014, 1–8.10.1155/2014/189164
   Web of Science ®Google Scholar
• Crawford, B., Soto, R., Olivares-Suarez, M., & Paredes, F. (2014b). A binary firefly algorithm for the set covering problem (pp. 65–73). Cham: Springer International Publishing.
   Google Scholar
• Cuesta, R., Crawford, B., Soto, R., & Paredes, F. (2014). An artificial bee colony algorithm for the set covering problem (pp. 53–63). Cham: Springer International Publishing.
   Google Scholar
• Demaine, E. D., Hajiaghayi, M., & Klein, P. N. (2009). Node-weighted steiner tree in planar graphs (pp. 328–340). Berlin Heidelberg: Springer.
   Google Scholar
• Fearnley, J., & Savani, R. (2015). The complexity of the simplex method (pp. 201–208). New York, NY: ACM.
   Google Scholar
• Gainer-Dewar, A., & Vera-Licona, P. (2017). The minimal hitting set generation problem: Algorithms and computation. SIAM Journal on Discrete, 31(1), 63–100.10.1137/15M1055024
   Web of Science ®Google Scholar
• Gendron, B., Lucena, A., da Cunha, A., & Simonetti, L. (2014). Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS Journal on Computing, 26(4), 645–657.10.1287/ijoc.2013.0589
   Web of Science ®Google Scholar
• Haddadi, S. (2017). Benders decomposition for set covering problems. Journal of Combinatorial Optimization, 33(1), 60–80.10.1007/s10878-015-9935-1
   Web of Science ®Google Scholar
• Jovanovic, R., & Tuba, M. (2011). An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Applied Soft Computing, 11(8), 530–5366.
   Web of Science ®Google Scholar
• Karp, R. M. (1972). Reducibility among combinatorial problems. Miller R.E., Thatcher J.W., Bohlinger J.D. (Ed.), Complexity of Computer Computations (pp. 85–103). Boston, MA: Springer, US.10.1007/978-1-4684-2001-2
   Google Scholar
• Kasirzadeh, A., Saddoune, M., & Soumis, F. (2017). Airline crew scheduling: Models, algorithms, and data sets. EURO Journal on Transportation and Logistics, 6(2), 111–137.10.1007/s13676-015-0080-x
   Web of Science ®Google Scholar
• Owais, M., Osman, M. K., & Moussa, G. (2016). Multi-objective transit route network design as set covering problem. IEEE Transactions on Intelligent Transportation Systems, 17(3), 670–679.10.1109/TITS.2015.2480885
   Web of Science ®Google Scholar
• Page, R. D. M., & Cotton, J. A. (2002). Vertebrate phylogenomics: Reconciled trees and gene duplications. Pacific Symposium on Biocomputing, 7, 536–547.
   Google Scholar
• Ren, Z. G., Feng, Z. R., Ke, L. J., & Zhang, Z. J. (2010). New ideas for applying ant colony optimization to the set covering problem. Computers & Industrial Engineering, 58(4), 774–784.10.1016/j.cie.2010.02.011
   Web of Science ®Google Scholar
• Safra, S., & Schwartz, O. (2003). On the complexity of approximating TSP with neighborhoods and related problems. European Symposium on Algorithms, 446–458.
   Google Scholar
• Slavík, P. (1997). Journal of Algorithms, A tight analysis of the greedy algorithm for set cover 25 (2), 237–254.10.1006/jagm.1997.0887
   Web of Science ®Google Scholar
• Soto, R., Crawford, B., Olivares, R., Barraza, J., Johnson, F., & Paredes, F. (2015). A binary cuckoo search algorithm for solving the set covering problem (pp. 88–97). Cham: Springer International Publishing.
   Google Scholar
• Srinivasan, A. (1999). Improved approximations guarantees for packing and covering integer programs. SIAM J. Comput., 29(2), 648–670.10.1137/S0097539796314240
   Web of Science ®Google Scholar
• Wang, Hongzhi, Belhassena, Amina, Zhang, L., & Yin, M. (2017). A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity. Science China Information Sciences, 388-389(6), 62–83.10.1016/j.ins.2017.01.016
   Web of Science ®Google Scholar
• Zhou, T., Lu, Z., Wang, Y., Ding, J., & Peng, B. (2015). Multi-start iterated tabu search for the minimum weight vertex cover problem. Journal of Combinatorial Optimization, 32(2), 1–17.
   Web of Science ®Google Scholar