Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)


Maximum Flow and Minimum Cut

by Joachim Reichel, Martin Skutella

We investigate the applicability of evolutionary algorithms for the maximum flow and minimum cut problem. It turns out that straightforward single-objective problem formulations are not suited for these problems. Therefore we present a bi-objective fitness function for SEMO and GSEMO that yields pseudopolynomial randomized algorithms for the minimum cut problem.

Back to mainpage