English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Conference Paper

Ant Colony Optimization and the Minimum Cut Problem

MPS-Authors
/persons/resource/persons44814

Kötzing,  Timo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44904

Lehre,  Per Kristian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45115

Neumann,  Frank
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Kötzing, T., Lehre, P. K., Neumann, F., & Oliveto, P. S. (2010). Ant Colony Optimization and the Minimum Cut Problem. In M. Pelikan, & J. Branke (Eds.), Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation (pp. 1393-1400). New York, NY: ACM.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-15FB-F
Abstract
Ant Colony Optimization (ACO) is a powerful metaheuristic for solving combinatorial optimization problems. With this paper we contribute to the theoretical understanding of this kind of algorithm by investigating the classical minimum cut problem. An ACO algorithm similar to the one that was proved successful for the minimum spanning tree problem is studied. Using rigorous runtime analyses we show how the ACO algorithm behaves similarly to Karger and Stein's algorithm for the minimum cut problem as long as the use of pheromone values is limited. Hence optimal solutions are obtained in expected polynomial time. On the other hand, we show that high use of pheromones has a negative effect, and the ACO algorithm may get trapped in local optima resulting in an exponential runtime to obtain an optimal solution. This result indicates that ACO algorithms may be inappropriate for finding minimum cuts.