A 2-Approximation Algorithm for Capacitated Partial Vertex Cover with Demands〔和文〕
スポンサーリンク
概要
- 論文の詳細を見る
頂点被覆問題は組合せ最適化問題の一種であり,NP-困難な問題として知られている.この問題は無向グラフG=(V,E)が与えられたとき,全ての辺について,少なくともどちらか一方の端点がCに含まれるような頂点部分集合C⫅Vで頂点の重みの合計が最小のものを求める問題である.この問題の一般化として,各頂点が被覆できる辺の本数に制限が加えられたり,ある決められた割合の辺だけ被覆することなどが考えられてきた.本稿では辺や頂点についてのさまざまな被覆条件を統合する一般化問題について考え,Submodular Set Coverアルゴリズムを用いることによって近似率2が保証できることを示す.
- 社団法人電子情報通信学会の論文
- 2003-01-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倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)