# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Ant Colony Optimization and the Minimum Cut Problem

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### 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 (*Proceedings
of 12th Annual Conference on Genetic and Evolutionary Computation* (pp. 1393-1400). New York, NY: ACM.

Cite as: http://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.