A two-pronged attack on the dragon of intractability

Stephen Gilmour*, Mark Dras

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

One approach to tractably finding a solution to an NP-complete optimisation problem is heuristic, where the solution is inexact but quickly found; another approach is to reduce the problem in such a way that the reduction has the same solution as the original but is simpler, and then to solve the reduction, noting that this reduction is still NP-complete. It is possible to combine the two approaches with the goal of taking advantage of both the speed of the heuristic approach and the exactness of the reduction, but this is typically done only in a simple way. The aim of this paper is to begin exploring the range of ways in which these two classes of approach can be combined, using vertex cover as a problem instance. We take as our reduction method the one used under parameterized complexity, where the problem is reduced through the application of kernelisation rules. For our heuristic we use Ant Colony Optimisation (ACO), where a set of 'ants' chooses a solution via distributed interaction; the search space 'terrain' that these ants traverse can be either flat or, as in a recent proposal, preconfigured by templates. In this paper, we investigate kernelisation rules as a notion of template that is richer than has previously been proposed, show that under three different models of combination the approach outperforms standard ACO for vertex cover, and analyse the solutions generated by the combination models with respect to each other.

Original languageEnglish
Title of host publicationProceeding ACSC '05 Proceedings of the Twenty-eighth Australasian conference on Computer Science
EditorsVladimir Estivill-Castro
Place of PublicationSydney, NSW
PublisherAustralian Computer Society
Pages183-192
Number of pages10
Volume38
ISBN (Print)1920682201, 9781920682200
Publication statusPublished - Feb 2005
Event28th Australasian Computer Science Conference, ACSC - 2005 - Newcastle, Australia
Duration: 31 Jan 20053 Feb 2005

Other

Other28th Australasian Computer Science Conference, ACSC - 2005
CountryAustralia
CityNewcastle
Period31/01/053/02/05

Fingerprint Dive into the research topics of 'A two-pronged attack on the dragon of intractability'. Together they form a unique fingerprint.

  • Cite this

    Gilmour, S., & Dras, M. (2005). A two-pronged attack on the dragon of intractability. In V. Estivill-Castro (Ed.), Proceeding ACSC '05 Proceedings of the Twenty-eighth Australasian conference on Computer Science (Vol. 38, pp. 183-192). Sydney, NSW: Australian Computer Society.