Revised analysis of the (1+1) EA for the minimum spanning tree problem

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We revisit the classical analysis of the (1+1) EA for the minimum spanning tree problem in the case that nothing is known about the weights of the underlying graph. Here the original upper bound on the expected running time by Neumann and Wegener [Theor. Comput. Sci. 378(1), 32-40, 2007], which depends on the largest weight of the graph, is of no use. The best upper bound available before in this case is due to Reichel and Skutella [FOGA 2009, 21-28] and is of order O(m3 \log n), where m is the number of edges and n the number of vertices. Using an adaptive drift analysis, we show the improved bound O(m2 (sqrt{c(G)} + \log n)), where c(G) is the circumference (length of the longest cycle) of the graph. This is only by an asymptotic factor of at most sqrt{n}/\log n away from the classical lower bound. Furthermore, an alternative fitness function leading to the bound O(m2\log n) is proposed, and limitations of the adaptive drift analysis are pointed out.
Original languageEnglish
Title of host publicationProceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14)
PublisherAssociation for Computing Machinery
Publication date2014
Pages509-516
ISBN (Electronic)978-1-4503-2662-9
DOIs
Publication statusPublished - 2014
EventGenetic and Evolutionary Computation Conference (GECCO 2014) - Vancouver, Canada
Duration: 12 Jul 201416 Jul 2014
http://www.sigevo.org/gecco-2014/index.html

Conference

ConferenceGenetic and Evolutionary Computation Conference (GECCO 2014)
CountryCanada
CityVancouver
Period12/07/201416/07/2014
Internet address

Keywords

  • Evolutionary Algorithms
  • Minimum Spanning Tree Problem
  • Runtime Analysis

Cite this

Witt, C. (2014). Revised analysis of the (1+1) EA for the minimum spanning tree problem. In Proceedings of the 2014 conference on Genetic and evolutionary computation (GECCO '14) (pp. 509-516). Association for Computing Machinery. https://doi.org/10.1145/2576768.2598237