More Web Proxy on the site http://driver.im/

research-article

The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation

Authors:

Per Kristian Lehre,

Frank NeumannAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 519 - 526

https://doi.org/10.1145/2463372.2463442

Published: 06 July 2013 Publication History

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] (2012) 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.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, 2011.

Digital Library

[2]

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. McGraw-Hill, 2nd edition, 2001.

Digital Library

[3]

K. Deb and A. Sinha. Solving bilevel multi-objective optimization problems using evolutionary algorithms. In M. Ehrgott, C. M. Fonseca, X. Gandibleux, J.-K. Hao, and M. Sevaux, editors, EMO, volume 5467 of Lecture Notes in Computer Science, pages 110--124. Springer, 2009.

Digital Library

[4]

K. Deb and A. Sinha. An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm. Evolutionary Computation, 18(3):403--449, 2010.

Digital Library

[5]

R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1999. 530 pp.

Digital Library

[6]

B. Hu and G. R. Raidl. An evolutionary algorithm with solution archive for the generalized minimum spanning tree problem. In R. Moreno-Díaz, F. Pichler, and A. Quesada-Arencibia, editors, EUROCAST (1), volume 6927 of Lecture Notes in Computer Science, pages 287--294. Springer, 2011.

Digital Library

[7]

B. Hu and G. R. Raidl. An evolutionary algorithm with solution archives and bounding extension for the generalized minimum spanning tree problem. In T. Soule and J. H. Moore, editors, GECCO, pages 393--400. ACM, 2012.

Digital Library

[8]

A. Koh. Solving transportation bi-level programs with differential evolution. In IEEE Congress on Evolutionary Computation, pages 2243--2250. IEEE, 2007.

[9]

S. Kratsch, P. K. Lehre, F. Neumann, and P. S. Oliveto. Fixed parameter evolutionary algorithms and maximum leaf spanning trees: A matter of mutation. In Proceedings of the Eleventh Conference on Parallel Problem Solving from Nature, pages 204--213, 2010.

Digital Library

[10]

S. Kratsch and F. Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. Algorithmica, 65(4):754--771, 2013.

Digital Library

[11]

F. Legillon, A. Liefooghe, and E.-G. Talbi. Cobra: A cooperative coevolutionary algorithm for bi-level optimization. In IEEE Congress on Evolutionary Computation, pages 1--8. IEEE, 2012.

[12]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[13]

Y.-S. Myung, C. ho Lee, and D. wan Tcha. On the generalized minimum spanning tree problem. Networks, 26(4):231--241, 1995.

[14]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization:Algorithms and Their Computational Complexity. Springer-Verlag New York, Inc., New York, NY, USA, 1st edition, 2010.

Digital Library

[15]

P. C. Pop. New models of the generalized minimum spanning tree problem. J. Math. Model. Algorithms, 3(2):153--166, 2004.

[16]

A. M. Sutton and F. Neumann. A parameterized runtime analysis of evolutionary algorithms for the euclidean traveling salesperson problem. In J. Hoffmann and B. Selman, editors, AAAI. AAAI Press, 2012. Extended technical report available at http://arxiv.org/abs/1207.0578.

[17]

A. M. Sutton and F. Neumann. A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. In Proceedings of the Twelfth Conference on Parallel Problem Solving from Nature (PPSN 2012), pages 52--61. Springer, 2012.

Digital Library

Cited By

Yan XNeumann ANeumann F(2024)Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular FunctionsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_2(20-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_2
Shi FYan XNeumann F(2022)Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling ProblemParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_37(526-541)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_37
Shi FNeumann FWang J(2021)Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problemTheoretical Computer Science10.1016/j.tcs.2021.09.003893(159-175)Online publication date: Nov-2021
https://doi.org/10.1016/j.tcs.2021.09.003
Show More Cited By

Index Terms

The generalized minimum spanning tree problem: a parameterized complexity analysis of bi-level optimisation
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A parameterised complexity analysis of bi-level optimisation with evolutionary algorithms

Bi-level optimisation problems have gained increasing interest in the field of combinatorial optimisation in recent years. In this paper, we analyse the runtime of some evolutionary algorithms for bi-level optimisation problems. We examine two NP-hard ...
The subdivision-constrained minimum spanning tree problem

Motivated by the constrained minimum spanning tree (CST) problem in Hassin and Levin [R. Hassin, A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, SIAM Journal on ...
Heuristic Search for the Generalized Minimum Spanning Tree Problem

The generalized minimum spanning tree (GMST) problem occurs in telecommunications network planning, where a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. The problem is known to be NP-hard, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
210
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yan XNeumann ANeumann F(2024)Sliding Window Bi-objective Evolutionary Algorithms for Optimizing Chance-Constrained Monotone Submodular FunctionsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70055-2_2(20-35)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70055-2_2
Shi FYan XNeumann F(2022)Runtime Analysis of Simple Evolutionary Algorithms for the Chance-Constrained Makespan Scheduling ProblemParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_37(526-541)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_37
Shi FNeumann FWang J(2021)Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problemTheoretical Computer Science10.1016/j.tcs.2021.09.003893(159-175)Online publication date: Nov-2021
https://doi.org/10.1016/j.tcs.2021.09.003
Shi FNeumann FWang JFriedrich TDoerr CArnold D(2019)Runtime analysis of evolutionary algorithms for the depth restricted (1,2)-minimum spanning tree problemProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3299904.3340314(133-146)Online publication date: 27-Aug-2019
https://dl.acm.org/doi/10.1145/3299904.3340314
Corus DLehre PNeumann FPourhassan M(2016)A parameterised complexity analysis of bi-level optimisation with evolutionary algorithmsEvolutionary Computation10.1162/EVCO_a_0014724:1(183-203)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1162/EVCO_a_00147
Neumann FSutton AEsparcia-Alcázar A(2015)Parameterized Complexity Analysis of Evolutionary AlgorithmsProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2756562(435-450)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2756562
Pourhassan MNeumann FEsparcia-Alcázar A(2015)On the Impact of Local Search Operators and Variable Neighbourhood Search for the Generalized Travelling Salesperson ProblemProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754656(465-472)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754656
Hu BWindbichler ARaidl G(2015)A New Solution Representation for the Firefighter ProblemEvolutionary Computation in Combinatorial Optimization10.1007/978-3-319-16468-7_3(25-35)Online publication date: 15-Mar-2015
https://doi.org/10.1007/978-3-319-16468-7_3
Neumann FSutton AArnold D(2014)Parameterized complexity analysis of evolutionary algorithmsProceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2598394.2605351(607-622)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2598394.2605351

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten