Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/102439
69 Visitors78 Hits0 Downloads
Kernelization as heuristic structure for the vertex cover problem
ANTS (5th : 2006) (4 - 7 September 2006 : Brussels)
Dorigo, Marco; Gambardella, Luca Maria; Birattari, Mauro; Martinoli, Alcherio; Poli, Riccardo and Thomas Stützle. Ant colony optimization and swarm intelligence : 5th international workshop, ANTS 2006, Brussels, Belgium, September 4-7, 2006 : proceedings, p.452-459
For solving combinatorial optimisation problems, exact methods accurately exploit the structure of the problem but are tractable only up to a certain size; approximation or heuristic methods are tractable for very large problems but may possibly be led into a bad solution. A question that arises is, From where can we obtain knowledge of the problem structure via exact methods that can be exploited on large-scale problems by heuristic methods? We present a framework that allows the exploitation of existing techniques and resources to integrate such structural knowledge into the Ant Colony System metaheuristic, where the structure is determined through the notion of kernelization from the field of parameterized complexity. We give experimental results using vertex cover as the problem instance, and show that knowledge of this type of structure improves performance beyond previously defined ACS algorithms.