一般化相互割当問題の上界値を求める分散ラグランジュ緩和プロトコル

• Item type: Journal(1)
• 公開日: 2006-05-15
• タイトル: 一般化相互割当問題の上界値を求める分散ラグランジュ緩和プロトコル
• タイトル / 言語: en
• タイトル: Distributed Lagrangean Relaxation Protocol that Computes an Upper Bound for the Generalized Mutual Assignment Problem
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：マルチエージェントの理論と応用
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: マルチエージェントの理論
• 著者所属: 神戸大学海事科学部
• 著者所属(英): en
• 著者所属(英): Faculty of Maritime Sciences, Kobe University
• 著者名: 平山, 勝敏
• 著者名(英): Katsutoshi, Hirayama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 一般化相互割当問題は，分散問題解決における問題を一般的に記述することができる組合せ最適化（最大化）問題である．従来，この問題に対して，最適値の下界を与える実行可能解を求めるプロトコルは提案されているが，最適値の上界を求めるプロトコルは存在しない．本論文では，そのような上界値を求めるプロトコルとしてDisLRPU を提案する．また，DisLRPU において，できるだけ小さい上界値を効率的に求めるための手法としてκ-sampling とlastsnap を提案し，ベンチマーク問題を用いた実験によりそれらの性能を評価する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The generalized mutual assignment problem (GMAP) is the combinatorial optimization (maximization) problem that can describe various distributed problem solving tasks. Recently, we have presented a communication protocol for this problem that enables the agents to find a feasible solution along with a lower bound. This paper provides a new protocol, called DisLRPU, where the agents are engaged in computing an upper bound rather than searching a feasible solution. Furthermore, to efficiently seek for a smaller upper bound using DisLRPU, we present two simple methods, called κ-sampling and lastsnap, and evaluate their performance empirically on benchmark instances.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 47, 号 5, p. 1415-1423, 発行日 2006-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764