direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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