Kernelization as heuristic structure for the vertex cover problem

Stephen Gilmour*, Mark Dras

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

16 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationAnt Colony Optimization and Swarm Intelligence - 5th International Workshop, ANTS 2006, Proceedings
EditorsMarco Dorigo, Luca Maria Gambardella, Mauro Birattari, Alcherio Martinoli, Riccardo Poli, Thomas Stützle
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages452-459
Number of pages8
ISBN (Electronic)9783540384830
ISBN (Print)3540384820, 9783540384823
DOIs
Publication statusPublished - Sept 2006
EventAnt Colony Optimization and Swarm Intelligence - 5th International Workshop, ANTS 2006, Proceedings - Brussels, Belgium
Duration: 4 Sept 20067 Sept 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4150 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

OtherAnt Colony Optimization and Swarm Intelligence - 5th International Workshop, ANTS 2006, Proceedings
Country/TerritoryBelgium
CityBrussels
Period4/09/067/09/06

Fingerprint

Dive into the research topics of 'Kernelization as heuristic structure for the vertex cover problem'. Together they form a unique fingerprint.

Cite this