Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Computing Minimum Cuts by Randomized Search Heuristics
Author(s): Neumann, Frank
Reichel, Joachim
Skutella, Martin
Type: Research Paper
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.
Subject(s): evolutionary algorithms
minimum s-t-cuts
multi-objective optimization
randomized search heuristics
Issue Date: 2008
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2008, 03
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 347.28 kB
DownloadShow Preview
Format: Unknown | Size: 301.31 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.