direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

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
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe