Authors: | Neumann, Frank Reichel, Joachim |
Title: | Approximating minimum multicuts by evolutionary multi-objective algorithms |
Language (ISO): | en |
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. |
URI: | http://hdl.handle.net/2003/26156 http://dx.doi.org/10.17877/DE290R-12771 |
Issue Date: | 2008-06 |
Appears in Collections: | Sonderforschungsbereich (SFB) 531 |
This item is protected by original copyright |
This item is protected by original copyright rightsstatements.org