Please use this identifier to cite or link to this item:
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)
Editor: Blum, C.
Statement of
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
DOI: 10.1145/2463372.2463442
Published version:
Appears in Collections:Aurora harvest
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access375.18 kBAdobe PDFView/Open

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