TY - GEN
T1 - Fixed Set Search Applied to the Minimum Weighted Vertex Cover Problem
AU - Jovanovic, Raka
AU - Voß, Stefan
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - Fixed set search (FSS) is a novel metaheuristic adding a learning mechanism to enhanced greedy approaches. In this paper we use FSS for solving the Minimum Weighted Vertex Cover Problem (MWVCP). First we define a Greedy Randomized Adaptive Search Procedure (GRASP) by randomizing the standard greedy constructive algorithm and combine it with a local search. The used local search is based on a simple downhill procedure. It checks if substituting a single or a pair of elements from a solution with ones that need to be added to keep the solution a vertex cover decreases the value of the objective function. The performance of the GRASP algorithm is improved by extending it towards FSS. Computational experiments performed on standard test instances from literature show that the proposed FSS algorithm for the MWVCP is highly competitive with state-of-the-art methods. Further, it is shown that the FSS manages to significantly improve the GRASP algorithm it is based on.
AB - Fixed set search (FSS) is a novel metaheuristic adding a learning mechanism to enhanced greedy approaches. In this paper we use FSS for solving the Minimum Weighted Vertex Cover Problem (MWVCP). First we define a Greedy Randomized Adaptive Search Procedure (GRASP) by randomizing the standard greedy constructive algorithm and combine it with a local search. The used local search is based on a simple downhill procedure. It checks if substituting a single or a pair of elements from a solution with ones that need to be added to keep the solution a vertex cover decreases the value of the objective function. The performance of the GRASP algorithm is improved by extending it towards FSS. Computational experiments performed on standard test instances from literature show that the proposed FSS algorithm for the MWVCP is highly competitive with state-of-the-art methods. Further, it is shown that the FSS manages to significantly improve the GRASP algorithm it is based on.
KW - Fixed set search
KW - GRASP
KW - Metaheuristics
KW - Minimum Weighted Vertex Cover Problem
UR - http://www.scopus.com/inward/record.url?scp=85076416635&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-34029-2_31
DO - 10.1007/978-3-030-34029-2_31
M3 - Conference contribution
AN - SCOPUS:85076416635
SN - 9783030340285
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 490
EP - 504
BT - Analysis of Experimental Algorithms - Special Event,SEA² 2019, Revised Selected Papers
A2 - Kotsireas, Ilias
A2 - Pardalos, Panos
A2 - Tsokas, Arsenis
A2 - Parsopoulos, Konstantinos E.
A2 - Souravlias, Dimitris
PB - Springer
T2 - Special Event on Analysis of Experimental Algorithms, SEA² 2019
Y2 - 24 June 2019 through 29 June 2019
ER -