Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/102439
30 Visitors
33 Hits
0 Downloads
- Title
- Kernelization as heuristic structure for the vertex cover problem
- Related
- ANTS (5th : 2006) (4 - 7 September 2006 : Brussels)
- Related
- 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
- DOI
- 10.1007/11839088_45
- Related
- Lecture notes in computer science Vol. 4150
- Publisher
- Berlin : Springer
- Date
- 2006
- FoR/RFCD Code(s)
-
080100 Artificial Intelligence and Image Processing
- Author/Creator
- Gilmour, Stephen
- Author/Creator
- Dras, Mark
- Description
- 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.
- Description
- 8 page(s)
- Subject Keyword
- 080100 Artificial Intelligence and Image Processing
- Resource Type
- conference paper
- Organisation
- Macquarie University. Dept. of Computing
- Identifier
- http://hdl.handle.net/1959.14/102439
- Identifier
- ISBN:9783540384823
- Identifier
- ISSN:0302-9743
- Identifier
- mq-rm-2006005480
- Language
- eng
- Reviewed
