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

Files in This Item:
File Description SizeFormat 
24908.pdfDNB211.31 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.