COMP2000-15 独立/連結な辺支配集合問題の近似可能性について
スポンサーリンク
概要
- 論文の詳細を見る
本稿では、辺支配集合に関連する問題の多項式時間近似特性について調べる。辺支配集合問題と最小極大マッチング問題は、一様辺重みの下では同じ近似特性を持ち、前者は、任意の重みの下でも2倍近似が可能であることが知られている。これに対し、最小重み極大マッチング問題を多項式時間計算可能な比率で近似することがNP-困難であることを示す。連結辺支配集合問題と連結点被覆問題も、一様辺重みの下では同じ近似特性を持ち、任意の重みの下でも、前者は3.598倍近似が可能であることが知られている。同問題の、(3+ε)倍近似アルゴリズムを示した後、最小重み連結点被覆問題が、(3+1n n)倍近似は可能であるが、NP⊂DTIME(n^<Ο(log log n)>)でない限り、(1-ε)1n n倍以下の近似は不可能であることを示す。
- 社団法人電子情報通信学会の論文
- 2000-06-19
著者
関連論文
- 連結頂点被覆問題および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倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)