Inhalt des Dokuments
Preprint 23-2008
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Approximating Minimum Multicuts by Evolutionary Multi-Objective Algorithms
- Authors
- Classification
-
not available
- Keywords
-
evolutionary algorithms, minimum multicuts, multi-objective optimization, randomized search heuristics
- 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.
- Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe