Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14425
For citation please use:
Main Title: Computing Minimum Cuts by Randomized Search Heuristics
Author(s): Neumann, Frank
Reichel, Joachim
Skutella, Martin
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15652
http://dx.doi.org/10.14279/depositonce-14425
License: http://rightsstatements.org/vocab/InC/1.0/
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:
Report-003-2008.pdf
Format: Adobe PDF | Size: 347.28 kB
DownloadShow Preview
Thumbnail
Report-003-2008.ps.gz
Format: Unknown | Size: 301.31 kB
Download

Item Export Bar

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