Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/65687
Citations
Scopus Web of Science® Altmetric
?
?
Type: Conference paper
Title: Ant colony optimization and the minimum cut problem
Author: Kotzing, T.
Lehre, P.
Neumann, F.
Oliveto, P.
Citation: Proceedings of the 12th annual conference on Genetic and evolutionary computation GECCO'10, held in Portland, Oregon, USA, 7-11 July 2010: pp. 1393-1400
Publisher: ACM Press
Publisher Place: New York
Issue Date: 2010
ISBN: 9781450300728
Conference Name: Genetic and Evolutionary Computation Conference (12th : 2010 : Portland, Oregon)
Editor: Pelikan, M.
Branke, J.
Statement of
Responsibility: 
Timo Kötzing, Per Kristian Lehre, Frank Neumann and Pietro S. Oliveto
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.
Keywords: Ant Colony Optimization
Min-cut
Rights: Copyright 2010 ACM
DOI: 10.1145/1830483.1830741
Published version: http://dx.doi.org/10.1145/1830483.1830741
Appears in Collections:Aurora harvest
Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.