Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  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

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-15FB-F Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0024-25D6-C
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kötzing, Timo1, Autor           
Lehre, Per Kristian1, Autor           
Neumann, Frank1, Autor           
Oliveto, Pietro S.2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 536747
DOI: 10.1145/1830483.1830741
Anderer: Local-ID: C1256428004B93B8-C042CD9C35F8A1EEC12577FA003B1657-Koe-Leh-Neu-Oli:c:10:AcoMinCut
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: 12th Annual Conference on Genetic and Evolutionary Computation
Veranstaltungsort: Portland, USA
Start-/Enddatum: 2010-07-07 - 2010-07-11

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation
  Kurztitel : GECCO 2010
Genre der Quelle: Konferenzband
 Urheber:
Pelikan, Martin1, Herausgeber
Branke, Jürgen1, Herausgeber
Affiliations:
1 External Organizations, ou_persistent22            
Ort, Verlag, Ausgabe: New York, NY : ACM
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 1393 - 1400 Identifikator: ISBN: 978-1-4503-0072-5