|Title:||Approximating minimum multicuts by evolutionary multi-objective algorithms|
|Abstract:||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.|
|Appears in Collections:||Sonderforschungsbereich (SFB) 531|
This item is protected by original copyright
All resources in the repository are protected by copyright.