Authors: Reichel, Joachim
Skutella, Martin
Title: Evolutionary algorithms and matroid optimization problems
Language (ISO): en
Abstract: We analyze teh performance fo evolutionary algorithms on various matroid optimization problems that encompass a vast number of efficiently solvable as well as NP-hard combinatorial optimization problems (including many well-known examples such as minimum spanning tree and maximum bipartite matching). We obtain very promising bounds on the expected running time and quality of the computed solution. Our results establish a better theoretical understanding of why randomized search heuristics yield empirically good results for many real-world problems.
Subject Headings: combinatorial algorithms
computations on discrete structures
evolutionary algorithms
matroid intersection
matroids
minimum weight basis
nonnumerical algorithms and problems
randomized search heuristics
URI: http://hdl.handle.net/2003/26132
http://dx.doi.org/10.17877/DE290R-8709
Issue Date: 2007-02
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
22507.pdfDNB202.88 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.