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 optimal solution in expected polynomial time.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Baier, G.: Flows with path restrictions. Ph.D. Thesis, TU Berlin (2003)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864–894 (1994)
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theor. Comput. Sci. 276, 51–81 (2002)
Duarte, A., Sánchez, Á., Fernández, F., Cabido, R.: A low-level hybridization between memetic algorithm and VNS for the max-cut problem. In: Proc. of GECCO ’05, pp. 999–1006 (2005)
Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. In: Proc. of GECCO ’07, pp. 797–804 (2007)
Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: Proc. of CEC ’03, pp. 1918–1925. IEEE Press, New York (2003)
Giel, O., Wegener, I.: Evolutionary algorithms and the maximum matching problem. In: Proc. of STACS ’03, pp. 415–426 (2003)
Horoba, C., Neumann, F.: Benefits and drawbacks for the use of epsilon-dominance in evolutionary multi-objective optimization. In: Proc. of GECCO ’08, pp. 641–648 (2008)
Jansen, T., Wegener, I.: Evolutionary algorithms—how to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Trans. Evol. Comput. 5(6), 589–599 (2001)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, 3rd edn. Springer, Berlin (2005)
Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining convergence and diversity in evolutionary multiobjective optimization. Evol. Comput. 10(3), 263–282 (2002)
Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Trans. Evol. Comput. 8(2), 170–182 (2004)
Liang, K.-H., Yao, X., Newton, C.S., Hoffman, D.: A new evolutionary approach to cutting stock problems with and without contiguity. Comput. Oper. Res. 29(12), 1641–1659 (2002)
Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. Eur. J. Oper. Res. 181(3), 1620–1629 (2007)
Neumann, F., Reichel, J.: Approximating minimum multicuts by evolutionary multi-objective algorithms. In: Proc. of PPSN’08, pp. 72–81 (2008)
Neumann, F., Reichel, J., Skutella, M.: Computing minimum cuts by randomized search heuristics. In: Proc. of GECCO ’08, pp. 779–786 (2008)
Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5(3), 305–319 (2006)
Neumann, F., Wegener, I.: Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theor. Comput. Sci. 378(1), 32–40 (2007)
Puchinger, J., Raidl, G.R., Koller, G.: Solving a real-world glass cutting problem. In: Proc. of EvoCOP ’04, pp. 165–176. Springer, Berlin (2004)
Reichel, J., Skutella, M.: Evolutionary algorithms and matroid optimization problems. In: Proc. of GECCO ’07, pp. 947–954 (2007)
Reichel, J., Skutella, M.: On the size of weights in randomized search heuristics. In: Proc. of FOGA ’09, pp. 21–28. ACM, New York (2009)
Siarry, P., Michalewicz, Z. (eds.): Advances in Metaheuristics for Hard Optimization. Natural Computing Series. Springer, Berlin (2008)
Witt, C.: Worst-case and average-case approximations by simple randomized search heuristics. In: Proc. of STACS ’05, pp. 44–56 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
A conference version appeared in GECCO 2008 [17].
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Neumann, F., Reichel, J. & Skutella, M. Computing Minimum Cuts by Randomized Search Heuristics. Algorithmica 59, 323–342 (2011). https://doi.org/10.1007/s00453-009-9370-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-009-9370-8