Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/83822
Citations
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.date.issued2013en
dc.identifier.citationProceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO'13, 2013 / pp.519-526en
dc.identifier.isbn9781450319638en
dc.identifier.urihttp://hdl.handle.net/2440/83822-
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.language.isoenen
dc.publisherACMen
dc.rightsCopyright 2013 ACMen
dc.source.urihttp://dl.acm.org/citation.cfm?id=2463372en
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.identifier.rmid0020137899en
dc.contributor.conferenceConference on Genetic and Evolutionary Computation (15th : 2013 : Amsterdam, Netherlands)en
dc.identifier.doi10.1145/2463372.2463442en
dc.publisher.placeonlineen
dc.identifier.pubid14635-
pubs.library.collectionComputer Science publicationsen
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
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.