Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Approximating Minimum Multicuts by Evolutionary Multi-objective Algorithms|
|Citation:||Parallel problem solving from nature - PPSN X : 10th International Conference, Dortmund, Germany, September 13-17, 2008 ; proceedings / Günter Rudolph... [et al.] (eds.), pp.72-81|
|Series/Report no.:||Lecture Notes in Computer Science|
|Conference Name:||Conference on Parallel Problem Solving from Nature (10th : 2008 : Dortmund, Germany)|
|Frank Neumann and Joachim Reichel|
|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.|
|Description:||Also published as a journal article: Lecture notes in computer science, 2008; 5199:72-81|
|Rights:||© Springer-Verlag Berlin Heidelberg 2008|
|Appears in Collections:||Computer Science publications|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.