TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2008

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 2008

Approximating Minimum Multicuts by Evolutionary Multi-Objective Algorithms
Zitatschlüssel Report-023-2008
Autor Frank Neumann and Joachim Reichel
Jahr 2008
Nummer 023
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung It has been shown that simple evolutionary algorithms are able to solve the minimum cut problem in expected polynomial time when using a multi-objective model of the problem. In this paper, we generalize these ideas to the NP-hard minimum multicut problem. Given a set of $k$ terminal pairs, we prove that evolutionary algorithms in combination with a multi-objective model of the problem are able to obtain a $k$-approximation for this problem in expected polynomial time.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe