Computing minimum cuts by 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 bi-criteria approach based on the famous maximum-flow minimum-cut theorem that enables evolutionary algorithms to find an optimum solution in expected polynomial time.

REFERENCES

• 1: G. Baier. Flows with Path Restrictions. PhD thesis, TU Berlin, 2003.
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 4: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7]
• 5: Abraham Duarte , Ángel Sánchez , Felipe Fernández , Raúl Cabido, A low-level hybridization between memetic algorithm and VNS for the max-cut problem, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068178]
• 6: Tobias Friedrich , Nils Hebbinghaus , Frank Neumann , Jun He , Carsten Witt, Approximating covering problems by randomized search heuristics using multi-objective models, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277118]
• 7: O. Giel. Expected runtimes of a simple multi-objective evolutionary algorithm. In Proc. of CEC '03, IEEE Press, pages 1918--1925, 2003.
• 8: Oliver Giel , Ingo Wegener, Evolutionary Algorithms and the Maximum Matching Problem, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.415-426, February 27-March 01, 2003
• 9: T. Jansen and I. Wegener. Evolutionary algorithms - how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. Evolutionary Computation, 5(6):589--599, 2001.
• 10: B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 3rd edition, 2005.
• 11: Marco Laumanns , Lothar Thiele , Kalyanmoy Deb , Eckart Zitzler, Combining convergence and diversity in evolutionary multiobjective optimization, Evolutionary Computation, v.10 n.3, p.263-282, Fall 2002 [doi>10.1162/106365602760234108]
• 12: M. Laumanns, L. Thiele, and E. Zitzler. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Trans. Evolutionary Computation, 8(2):170--182, 2004.
• 13: Ko-Hsin Liang , Xin Yao , Charles Newton , David Hoffman, A new evolutionary approach to cutting stock problems with and without contiguity, Computers and Operations Research, v.29 n.12, p.1641-1659, October 2002 [doi>10.1016/S0305-0548(01)00039-9]
• 14: F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. European Journal of Operational Research, 181(3):1620--1629, 2007.
• 15: Frank Neumann , Ingo Wegener, Minimum spanning trees made easier via multi-objective optimization, Natural Computing: an international journal, v.5 n.3, p.305-319, September 2006 [doi>10.1007/s11047-006-9004-x]
• 16: Frank Neumann , Ingo Wegener, Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theoretical Computer Science, v.378 n.1, p.32-40, June, 2007 [doi>10.1016/j.tcs.2006.11.002]
• 17: J. Puchinger, G. R. Raidl, and G. Koller. Solving a real-world glass cutting problem. In Proc. of EvoCOP '04, pages 165--176. Springer, 2004.
• 18: Joachim Reichel , Martin Skutella, Evolutionary algorithms and matroid optimization problems, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277149]
• 19: C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS '05, pages 44--56, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
evolutionary algorithms, minimum s-t-cuts, multi-objective optimization, randomized search heuristics