Authors: Giel, Oliver
Wegener, Ingo
Title: Evolutionary Algorithms and the Maximum Matching Problem
Language (ISO): en
Abstract: Randomized search heuristics like evolutionary algorithms are mostly applied to problems whose structure is not completely known but also to combinatorial optimization problems. Practitioners report surprising successes but almost no results with theoretically well-founded analyses exist. Such an analysis is started in this paper for a fundamental evolutionary algorithm and the well-known maximum matching problem. It is proven that the evolutionary algorithm is a polynomial-time randomized approximation scheme (PRAS) for this optimization problem, although the algorithm does not employ the idea of augmenting paths. Moreover, for very simple graphs it is proved that the expected optimization time of the algorithm is polynomially bounded and bipartite graphs are constructed where this time grows exponentially.
URI: http://hdl.handle.net/2003/5432
http://dx.doi.org/10.17877/DE290R-5774
Issue Date: 2003-12-23
Publisher: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
142.pdfDNB325.31 kBAdobe PDFView/Open
142.ps645.04 kBPostscriptView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.