 |
    |
Randomized Local Search, Evolutionary Algorithms, and the Minimum Spanning Tree Problem
Frank Neumann1 and Ingo Wegener*2
1Inst. für Informatik und Prakt. Mathematik, Christian-Albrechts-Univ. zu Kiel, 24098 Kiel, Germany
fne@informatik.uni-kiel.de
2FB Informatik, LS 2, Univ. Dortmund, 44221 Dortmund, Germany
ingo.wegener@uni-dortmund.de
Abstract. Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.
*This work was supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the Collaborative Research Center “Computational Intelligence” (SFB 531) and by the German-Israeli Foundation (GIF) in the project “Robustness Aspects of Algorithms”.
LNCS 3102, p. 713 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004