Abstract
The minimum weight vertex cover problem is a basic combinatorial optimization problem defined as follows. Given an undirected graph and positive weights for all vertices the objective is to determine a subset of the vertices which covers all edges such that the sum of the related cost values is minimized. In this paper we apply a modified reactive tabu search approach for solving the problem. While the initial concept of reactive tabu search involves a random walk we propose to replace this random walk by a controlled simulated annealing. Numerical results are presented outperforming previous metaheuristic approaches in most cases.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
CPU times for the approaches reported in Table 1 can be found in the original references. Here we summarize times for the instances in the table and computing environments as they are reported in literature. ACO (Shyu et al. 2004) was run on a PC with AMD 1.7 GHz CPU and 256 MB RAM. CPU times vary between 4.3 and 6.6 seconds. HSSGA (Singh and Gupta 2006) was executed on a Pentium 4, 2.4 GHz system with 512 MB RAM. CPU times vary between 1.2 and 4.0 seconds. Computation times of the pilot method (Voß et al. 2005) were considerably larger using a Pentium IV with 1.8 GHz. They start at about 20 seconds per problem instance for an evaluation depth of 1 and scale linearly for the considered range of an evaluation depth value of 20. The modified ACO of Jovanovic and Tuba (2011) has been performed on an Intel Core 2 Duo CPU 8500, 4 GHz with 4 GB RAM. Specific CPU times were not reported.
References
Balaji, S., Swaminathan, V., Kannan, K.: An effective algorithm for minimum weighted vertex cover problem. Int. J. Comput. Math. Sci. 4, 34–38 (2010)
Battiti, R.: Reactive search: toward self-tuning heuristics. In: Rayward-Smith, V.J., Osman, I.H., Reeves, C.R., Smith, G.D. (eds.) Modern Heuristic Search Methods, pp. 61–83. Wiley, Chichester (1996)
Battiti, R., Tecchiolli, G.: The reactive tabu search. ORSA J. Comput. 6, 126–140 (1994)
Caserta, M., Voß, S.: Metaheuristics: intelligent problem solving. In: Maniezzo, V., Stützle, T., Voß, S. (eds.) Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, pp. 1–38. Springer, Berlin (2009)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex-cover. Ann. Math. 162, 439–485 (2005)
Fink, A., Voß, S.: HotFrame: a heuristic optimization framework. In: Voß, S., Woodruff, D.L. (eds.) Optimization Software Class Libraries, pp. 81–154. Kluwer, Boston (2002)
Gilmour, S., Dras, M.: Kernelization as heuristic structure for the vertex cover problem. Lect. Notes Comput. Sci. 4150, 452–459 (2006)
Glover, F., Laguna, M.: Tabu Search. Kluwer, Dordrecht (1997)
Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V.R.: Experimental analysis of approximation algorithms for the vertex cover and set covering problems. Comput. Oper. Res. 33, 3520–3534 (2006)
Johnson, D.S., Aragon, C.R., McGeoch, L.A., Schevon, C.: Optimization by simulated annealing: an experimental evaluation; part I, graph partitioning. Oper. Res. 37, 865–892 (1989)
Jovanovic, R., Tuba, M.: An ant colony optimization algorithm with improved pheromone correction strategy for the minimum weight vertex cover problem. Appl. Soft Comput. 11, 5360–5366 (2011)
Jovanovic, R., Tuba, M., Simian, D.: Comparison of different topologies for island-based multi-colony ant algorithms for the minimum weight vertex cover problem. WSEAS Trans. Comput. 9, 83–92 (2010)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2-ϵ. J. Comput. Syst. Sci. 74, 335–349 (2008)
Kirkpatrick, S., Gelatt, C. Jr., Vecchi, M.: Optimization by simulated annealing. Science 220, 671–680 (1983)
Shyu, S.J., Yin, P.-Y., Lin, B.M.T.: An ant colony optimization algorithm for the minimum weight vertex cover problem. Ann. Oper. Res. 131, 283–304 (2004)
Singh, A., Gupta, A.K.: A hybrid heuristic for the minimum weight vertex cover problem. Asia-Pac. J. Oper. Res. 23, 273–285 (2006)
Voß, S., Fink, A.: Hybridizing reactive tabu search with simulated annealing. Lect. Notes Comput. Sci. 7219, 509–512 (2012)
Voß, S., Fink, A., Duin, C.: Looking ahead with the pilot method. Ann. Oper. Res. 136, 285–302 (2005)
Acknowledgements
An earlier version of this paper was presented at the MIC 2007. An extended abstract with results on the ring load balancing problem was presented at the LION 2012 conference (Voß and Fink 2012).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Voß, S., Fink, A. A hybridized tabu search approach for the minimum weight vertex cover problem. J Heuristics 18, 869–876 (2012). https://doi.org/10.1007/s10732-012-9211-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-012-9211-9