Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/66822
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: Approximating Minimum Multicuts by Evolutionary Multi-objective Algorithms
Author: Neumann, F.
Reichel, J.
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
Publisher: Springer
Publisher Place: Berlin
Issue Date: 2008
Series/Report no.: Lecture Notes in Computer Science
ISBN: 3540876995
9783540876991
ISSN: 0302-9743
1611-3349
Conference Name: Conference on Parallel Problem Solving from Nature (10th : 2008 : Dortmund, Germany)
Statement of
Responsibility: 
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
RMID: 0020107066
DOI: 10.1007/978-3-540-87700-4_8
Published version: https://doi.org/10.1007/978-3-540-87700-4
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.