Adelaide Research & Scholarship
Please use this identifier to cite or link to this item:
https://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) |
| Editor: | Rudolph, G. Jansen, T. Lucas, S. Poloni, C. Beume, N. |
| 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 |
| DOI: | 10.1007/978-3-540-87700-4_8 |
| Published version: | http://dx.doi.org/10.1007/978-3-540-87700-4_8 |
| Appears in Collections: | Aurora harvest 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.