Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Full metadata record
DC FieldValueLanguage
dc.contributor.authorCorus, D.en
dc.contributor.authorLehre, P.en
dc.contributor.authorNeumann, F.en
dc.identifier.citationProceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO'13, 2013 / pp.519-526en
dc.description.abstractBi-level optimisation problems have gained increasing inter- est in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolu- tionary algorithms for bi-level optimisation problems. We examine the NP-hard generalised minimum spanning tree problem and analyse the two approaches presented by Hu and Raidl [7] in the context of parameterised complexity (with respect to the number of clusters) that distinguish each other by the chosen representation of possible solutions. Our results show that a (1+1) EA working with the spanning nodes representation is not a fixed-parameter evolutionary algorithm for the problem, whereas the global structure rep- resentation enables to solve the problem in fixed-parameter time. Furthermore, we present hard instances for each ap- proach and show that the two approaches are highly com- plementary by proving that they solve each other’s hard in- stances very efficiently.en
dc.description.statementofresponsibilityDogan Corus, Per Kristian Lehre, Frank Neumannen
dc.rightsCopyright 2013 ACMen
dc.subjectBi-level Optimisation; Evolutionary Algorithms; Combinatorial Optimisationen
dc.titleThe generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisationen
dc.typeConference paperen
dc.contributor.conferenceConference on Genetic and Evolutionary Computation (15th : 2013 : Amsterdam, Netherlands)en
pubs.library.collectionComputer Science publicationsen
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]en
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_83822.pdfRestricted Access375.18 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.