日本語
 
Help Privacy Policy ポリシー/免責事項
  詳細検索ブラウズ

アイテム詳細

登録内容を編集ファイル形式で保存
 
 
ダウンロード電子メール
 タグ情報を表示リリース履歴を表示詳細要約
  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

 

表示: 全項目 非表示: 全項目

基本情報

表示: 非表示:
アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-15FB-F 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0024-25D6-C
資料種別: 会議論文

ファイル

表示: ファイル

関連URL

表示:

作成者

表示:
非表示:
 作成者:
Kötzing, Timo1, 著者           
Lehre, Per Kristian1, 著者           
Neumann, Frank1, 著者           
Oliveto, Pietro S.2, 著者
所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

内容説明

表示:
非表示:
キーワード: -
 要旨: 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.

資料詳細

表示:
非表示:
言語: eng - English
 日付: 2010
 出版の状態: 出版
 ページ: -
 出版情報: -
 目次: -
 査読: -
 識別子（DOI, ISBNなど）: eDoc: 536747
DOI: 10.1145/1830483.1830741
その他: Local-ID: C1256428004B93B8-C042CD9C35F8A1EEC12577FA003B1657-Koe-Leh-Neu-Oli:c:10:AcoMinCut
 学位: -

関連イベント

表示:
非表示:
イベント名: 12th Annual Conference on Genetic and Evolutionary Computation
開催地: Portland, USA
開始日・終了日: 2010-07-07 - 2010-07-11

訴訟

表示:

Project information

表示:

出版物 1

表示:
非表示:
出版物名: Proceedings of 12th Annual Conference on Genetic and Evolutionary Computation
  省略形 : GECCO 2010
種別: 会議論文集
 著者・編者:
Pelikan, Martin1, 編集者
Branke, Jürgen1, 編集者
所属:
1 External Organizations, ou_persistent22            
出版社, 出版地: New York, NY : ACM
ページ: - 巻号: - 通巻号: - 開始・終了ページ: 1393 - 1400 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-1-4503-0072-5