2値重み集合被覆問題に対する貪欲法の改良について
スポンサーリンク
概要
- 論文の詳細を見る
集合被覆問題とは,資源選択問題などをモデル化した問題であり,NP完全な問題であることが知られている.この問題は要素の集合UとUの重みつき部分集合の族が与えられたとき,Uのすべての要素を被覆する重みの合計が最小の部分集合族を求める問題でる.特に,部分集合の最大サイズがκである集合被覆問題はκ集合被覆問題と呼ばれ,貪欲法によりE(κ)Σ^κ_i=1(1/i)の近似保証が得られることが知られている。又,任意の重み付きの場合については,これよりも良い近似保証のものは知られていない.そこで,本稿では重みが2種類の場合の3-集合被覆問題を対象とする.重みが1と2以上の場合については近似保証がH(3)-1/6となることが以前に示されている。従って,本稿では重みが1と1.5以上3以下の定数の2種類の場合について考え,この場合についても貪欲法を改良することにより,同様にH(3)-1/6の近似保証が得られるということを線形計画法とその双対を用いて示す.
- 2002-05-17
著者
関連論文
- 連結頂点被覆問題および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倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)