Approximating Minimum Multicuts by Evolutionary Multi-objective Algorithms
Date
2008
Authors
Neumann, F.
Reichel, J.
Editors
Rudolph, G.
Jansen, T.
Lucas, S.
Poloni, C.
Beume, N.
Jansen, T.
Lucas, S.
Poloni, C.
Beume, N.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
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
Statement of Responsibility
Frank Neumann and Joachim Reichel
Conference Name
Conference on Parallel Problem Solving from Nature (10th : 2008 : Dortmund, Germany)
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.
School/Discipline
Dissertation Note
Provenance
Description
Also published as a journal article: Lecture notes in computer science, 2008; 5199:72-81
Access Status
Rights
© Springer-Verlag Berlin Heidelberg 2008