d-claw freeグラフ上の独立集合問題に対する局所探索法について
スポンサーリンク
概要
- 論文の詳細を見る
グラフの独立集合問題は,多項式時間では近似することすら難しいNP困難問題であるが,d-claw freeグラフ上では,自然な局所探索法により(d-1+ε)/2(ε>0)の倍近似できることが知られている.しかし,重みつき独立集合問題に対しては,同手法の有効性は失われ,近似性能は負欲法程度にまで劣化する.同問題に対する現在最良の近似アルゴリズムは,d/2を保証するΩ(n^d)時間アルゴリズム,もしくは,任意のdで多項式である2(d-1)/3倍アルゴリズムであり,いずれも局所探索法であるが,問題の目的関数とは異なる評価関数を用いている.本論文では,重み分布に制限のある条件下で,同問題に対する標準的局所探索法の有効性を検証する.
- 社団法人電子情報通信学会の論文
- 2010-03-05
著者
-
藤戸 敏弘
豊橋技術科学大学
-
北山 数行
豊橋技術科学大学大学院工学研究科情報工学専攻
-
藤戸 敏弘
豊橋技術科学大学大学院工学研究科情報工学専攻
-
藤戸 敏弘
名古屋大学大学院工学研究科
-
藤戸 敏弘
豊橋技術科学大学大学院工学研究科情報・知能工学専攻
関連論文
- 連結頂点被覆問題およびtree cover問題に対する2倍近似並列アルゴリズム
- 多状態スキーレンタル問題に対する最適競合比の解析
- データ構造とアルゴリズム, 杉原厚吉(著), "データ構造とアルゴリズム",共立出版(2001-12);A5判, 定価(本体2,200円+税)
- d-claw freeグラフ上の独立集合問題に対する局所探索法について
- 2値重み集合被覆問題に対する貪欲法の改良について
- 重みが1と2の集合被覆問題に対する貪欲法の改良
- 劣モジュラ被覆問題の近似について
- 層別グラフにおける有向木被覆問題の近似について (理論計算機科学の深化と応用)
- 最小コスト木状被覆問題の2倍近似アルゴリズム
- 重みつき集合充填問題に対する局所改善法について
- 集合多重被覆問題に対する貪欲法の改良
- 被覆容量/要求回数付き部分頂点被覆問題の2倍近似解法(アルゴリズム理論)
- A 2-Approximation Algorithm for Capacitated Partial Vertex Cover with Demands〔和文〕
- COMP2000-15 独立/連結な辺支配集合問題の近似可能性について
- 辺支配集合問題の2倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)
- 2011年度冬のLAシンポジウム Approximating Steiner Tree and Tree Cover problems in Directed Graphs (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
- 木状泥棒領域を持つグラフ護衛問題の近似
- 木状泥棒領域を持つグラフ護衛問題の近似
- 初等的二部グラフで構成される木における恒久的頂点被覆数について(一般)