Autor(en): Neumann, Frank
Reichel, Joachim
Skutella, Martin
Titel: Computing minimum cuts by randomized search heuristics
Sprache (ISO): en
Zusammenfassung: We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bicriteria approach based on the famous MaxFlow-MinCut Theorem that enables evolutionary algorithms to find an optimum solution in expected polynomial time.
Schlagwörter: analysis of algorithms and problem complexity
evolutionary algorithms
minimum s-t-cuts
multiobjective optimization
performance
randomized search heuristics
theory of computation
URI: http://hdl.handle.net/2003/26149
http://dx.doi.org/10.17877/DE290R-9023
Erscheinungsdatum: 2008-02
Enthalten in den Sammlungen:Sonderforschungsbereich (SFB) 531

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
24208.pdfDNB390.32 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org