A hybridized tabu search approach for the minimum weight vertex cover problem

Link:
Autor/in:
Erscheinungsjahr:
2012
Medientyp:
Text
Schlagworte:
  • Metaheuristics
  • Minimum weight vertex cover problem
  • Reactive tabu search
  • Simulated annealing
Beschreibung:
  • 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. © 2012 Springer Science+Business Media, LLC.
Lizenz:
  • info:eu-repo/semantics/closedAccess
Quellsystem:
Forschungsinformationssystem der UHH
Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/b0f2a32b-a8b0-4687-98c8-38d03bae3968