多点対カット問題に対する集合被覆アプローチに基づく近似解法

• Item type: SIG Technical Reports(1)
• 公開日: 2008-01-23
• タイトル: 多点対カット問題に対する集合被覆アプローチに基づく近似解法
• タイトル / 言語: en
• タイトル: A Heuristic Algorithm based on the Set Covering Approach for the Multicut Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋大学
• 著者所属: 名古屋大学
• 著者所属: 名古屋大学
• 著者所属: 名古屋大学
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者名: 木本, 大介; 柳浦睦憲; 小野, 孝男; 平田, 富夫
• 著者名(英): Daisuke, KIMOTO; Mutsunori, YAGIURA; Takao, ONO; Tomio, HIRATA
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多点対カット問題はターミナル対が3つ以上の場合，NP困難であることが知られている．各ターミナル対間の経路を列挙し，その経路をカットするために必要な辺を考えることで，多点対カット問題を集合被覆問題に帰着できるが，本研究では，この考え方に基づいて近似解を求めるアルゴリズムを提案し，その性能を実験的に評価する．ターミナル対間の全経路を列挙するのは現実的ではないので，提案手法では，一部の経路からなる集合被覆問題を考え，そのラグランジュ緩和から得られる情報を利用したヒューリスティクスで近似解を求める．計算実験の結果，提案手法の有効性を確認できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The multicut problem is known to be NP-hard when the number of terminal pairs is three or more. Multicut problem can be reduced to the set covering problem (SCP) by enumerating paths between each terminal pairs and considering necessary edges to cut such paths. In this paper, we propose a heuristic algorithm based on this idea, in which a Lagrangian heuristic algorithm is used to obtain approximate solutions of SCP. Note that the algorithm maintains a manageable number of paths, because it is impractical to enumerate all paths between each terminal pairs. Through computational experiments, we confirm the effectiveness of our algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2008, 号 6(2008-AL-116), p. 47-53, 発行日 2008-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会