Paper Info
Title
Revised analysis of the (1+1) ea for the minimum spanning tree problem
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.
Year
DOI
Venue
2014
10.1145/2576768.2598237
GECCO
Keywords
Field
DocType
evolutionary algorithms,general,minimum spanning tree problem,runtime analysis
Binary logarithm,Circumference,Graph,Combinatorics,Mathematical optimization,Vertex (geometry),Upper and lower bounds,Fitness function,Spanning tree,Mathematics,Minimum spanning tree
Conference
Citations 
PageRank 
References 
3
0.36
11
Authors
1
Name
Order
Citations
PageRank
Carsten Witt198759.83