Computing minimum cuts by randomized search heuristics

Neumann, Frank; Reichel, Joachim; Skutella, Martin

Computing minimum cuts by randomized search heuristics

dc.contributor.author	Neumann, Frank	de
dc.contributor.author	Reichel, Joachim	de
dc.contributor.author	Skutella, Martin	de
dc.date.accessioned	2009-05-12T16:01:48Z
dc.date.available	2009-05-12T16:01:48Z
dc.date.issued	2008-02	de
dc.description.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.	en
dc.identifier.uri	http://hdl.handle.net/2003/26149
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-9023
dc.language.iso	en	de
dc.relation.ispartofseries	Reihe CI; 242-08	de
dc.subject	analysis of algorithms and problem complexity	en
dc.subject	evolutionary algorithms	en
dc.subject	minimum s-t-cuts	en
dc.subject	multiobjective optimization	en
dc.subject	performance	en
dc.subject	randomized search heuristics	en
dc.subject	theory of computation	en
dc.subject.ddc	004	de
dc.title	Computing minimum cuts by randomized search heuristics	en
dc.type	Text	de
dc.type.publicationtype	report	de
dcterms.accessRights	open access

Files

Original bundle

Now showing 1 - 1 of 1

Name:: 24208.pdf
Size:: 390.32 KB
Format:: Adobe Portable Document Format
Description:: DNB

Download

Collections

Sonderforschungsbereich (SFB) 531