direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 03-2008

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
Computing Minimum Cuts by Randomized Search Heuristics
Authors
Publication
An extended abstract appeared in Proceedings of the 10th Genetic and Evolutionary Computation Conference (GECCO'08), 779-787, 2008.
Classification
not available
Keywords
evolutionary algorithms, minimum s-t-cuts, multi-objective optimization, randomized search heuristics
Abstract
We study the minimum s-t-cut problem in graphs with costs on the edges in the context of evolutionary algorithms. Minimum cut problems belong to the class of basic network optimization problems that occur as crucial subproblems in many real-world optimization problems and have a variety of applications in several different areas. We prove that there exist instances of the minimum s-t-cut problem that cannot be solved by standard single-objective evolutionary algorithms in reasonable time. On the other hand, we develop a bicriteria approach based on the famous MaxFlow-MinCut Theorem that enables evolutionary algorithms to find an optimum solution in expected polynomial time.
Source
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe