Autor(en): | Reichel, Joachim Skutella, Martin |
Titel: | Evolutionary algorithms and matroid optimization problems |
Sprache (ISO): | en |
Zusammenfassung: | 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. |
Schlagwörter: | 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 |
Erscheinungsdatum: | 2007-02 |
Enthalten in den Sammlungen: | Sonderforschungsbereich (SFB) 531 |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
22507.pdf | DNB | 202.88 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org