Approximating Minimum Multicuts by Evolutionary Multi-Objective Algorithms
| dc.contributor.author | Neumann, Frank | |
| dc.contributor.author | Reichel, Joachim | |
| dc.date.accessioned | 2021-12-17T10:07:51Z | |
| dc.date.available | 2021-12-17T10:07:51Z | |
| dc.date.issued | 2008 | |
| dc.description.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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15636 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14409 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | evolutionary algorithms | en |
| dc.subject.other | minimum multicuts | en |
| dc.subject.other | multi-objective optimization | en |
| dc.subject.other | randomized search heuristics | en |
| dc.title | Approximating Minimum Multicuts by Evolutionary Multi-Objective Algorithms | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2008, 23 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |