文献

J-GLOBAL ID：201002282214078218   整理番号：10A0444813

d-claw freeグラフ上の独立集合問題に対する局所探索法について

On the standard local search for the independent set problem in d-claw free graphs

著者 (2件)： 北山数行 (豊橋技科大 大学院工学研究科) ,  藤戸敏弘 (豊橋技科大 大学院工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 109  号： 465(COMP2009 49-58)  ページ： 33-38  発行年： 2010年03月05日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： グラフの独立集合問題は,多項式時間では近似することすら難しいNP困難問題であるが,d-claw freeグラフ上では,自然な局所探索法により(d-1+ε)/2(ε>0)倍近似できることが知られている。しかし,重みつき独立集合問題に対しては,同手法の有効性は失われ,近似性能は貪欲法程度にまで劣化する。同問題に対する現在最良の近似アルゴリズムは,d/2を保証するΩ(n^d)時間アルゴリズム,もしくは,任意のdで多項式である2(d-1)/3倍アルゴリズムであり,いずれも局所探索法であるが,問題の目的関数とは異なる評価関数を用いている。本論文では,重み分布に制限のある条件下で,同問題に対する標準的局所探索法の有効性を検証する。(著者抄録)

シソーラス用語： *近傍探索法 ,  計算機アルゴリズム ,  *目的関数 ,  *評価関数 ,  点検 ,  問題 ,  *NP完全問題
準シソーラス用語： *近似アルゴリズム ,  *独立集合 ,  有効性確認 ,  貪欲法

分類 (1件)： 数値計算  (JE02000J)

引用文献 (12件)：

• ARKIN, E. M. On local search for weighted packing problems. Mathematics of Operations Research. 1998, 23, 640-648
• BAFNA, V. Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles). Discrete Applied Mathematics. 1996, 71, 41-53
• BERMAN, P. A d/2 approximation for maximum weight independent set in d-claw free graphs. Nordic Journal of Computing. 2000, 7, 3, 178-184
• BERMAN, P. On approximation properties of the independent set problem for low degree graphs. Theory Computing Systems. 1999, 32, 2, 115-132
• BERMAN, P. Optimizing misdirection. Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003. 2003, 192-201

タイトルに関連する用語 (3件)： グラフ ,  集合 ,  局所探索法