Loading…
Approximating Minimum Multicuts by Evolutionary Multi-Objective Algorithms
Neumann, Frank; Reichel, Joachim
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
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.
