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
minimum weight basis
nonnumerical algorithms and problems
randomized search heuristics
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

If no CC-License is given, pleas contact the the creator, if you want to use thre resource other than only read it.