English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Ant Colony Optimization and the Minimum Cut Problem

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-15FB-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-25D6-C
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kötzing, Timo1, Author           
Lehre, Per Kristian1, Author           
Neumann, Frank1, Author           
Oliveto, Pietro S.2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 536747
DOI: 10.1145/1830483.1830741
Other: Local-ID: C1256428004B93B8-C042CD9C35F8A1EEC12577FA003B1657-Koe-Leh-Neu-Oli:c:10:AcoMinCut
 Degree: -

Event

show
hide
Title: 12th Annual Conference on Genetic and Evolutionary Computation
Place of Event: Portland, USA
Start-/End Date: 2010-07-07 - 2010-07-11

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation
  Abbreviation : GECCO 2010
Source Genre: Proceedings
 Creator(s):
Pelikan, Martin1, Editor
Branke, Jürgen1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 1393 - 1400 Identifier: ISBN: 978-1-4503-0072-5