Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/83822
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation
Author: Corus, D.
Lehre, P.
Neumann, F.
Citation: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, GECCO'13, 2013 / pp.519-526
Publisher: ACM
Publisher Place: online
Issue Date: 2013
ISBN: 9781450319638
Conference Name: Conference on Genetic and Evolutionary Computation (15th : 2013 : Amsterdam, Netherlands)
Statement of
Responsibility: 
Dogan Corus, Per Kristian Lehre, Frank Neumann
Abstract: Bi-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.
Keywords: Bi-level Optimisation; Evolutionary Algorithms; Combinatorial Optimisation
Rights: Copyright 2013 ACM
RMID: 0020137899
DOI: 10.1145/2463372.2463442
Published version: http://dl.acm.org/citation.cfm?id=2463372
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.