Neumann, FrankReichel, Joachim2021-12-172021-12-1720082197-8085https://depositonce.tu-berlin.de/handle/11303/15636http://dx.doi.org/10.14279/depositonce-14409It 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.en510 Mathematikevolutionary algorithmsminimum multicutsmulti-objective optimizationrandomized search heuristicsResearch Paper