The generalized minimum spanning tree problem: A parameterized complexity analysis of Bi-level optimisation

Dogan Corus, Per Kristian Lehre, Frank Neumann

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

6 Citations (Scopus)

Abstract

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. With this paper, we start the runtime analysis of evolutionary 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 representation enables to solve the problem in fixed-parameter time. Furthermore, we present hard instances for each approach and show that the two approaches are highly complementary by proving that they solve each other's hard instances very efficiently.

Original languageEnglish
Title of host publicationGECCO 2013 - Proceedings of the 2013 Genetic and Evolutionary Computation Conference
Pages519-525
Number of pages7
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 15th Genetic and Evolutionary Computation Conference, GECCO 2013 - Amsterdam, Netherlands
Duration: 6 Jul 201310 Jul 2013

Conference

Conference2013 15th Genetic and Evolutionary Computation Conference, GECCO 2013
Country/TerritoryNetherlands
CityAmsterdam
Period6/07/1310/07/13

Keywords

  • Bi-level optimisation
  • Combinatorial optimisation
  • Evolutionary algorithms

ASJC Scopus subject areas

  • Genetics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'The generalized minimum spanning tree problem: A parameterized complexity analysis of Bi-level optimisation'. Together they form a unique fingerprint.

Cite this