劣モジュラ被覆問題の近似について
スポンサーリンク
概要
- 論文の詳細を見る
劣モジュラ被覆問題に対する多項式時間ヒューリスティックをプライマル-デュアル法に基づいて設計する。求まる解の(最適解に対する)近似比を解析し、通常の集合被覆問題におけるものの一般形として与える。この応用として、点重みと辺容量のある超グラフにおける点部分被覆問題を取り上げ、最大辺の大きさをdとすると、最適解の高々d倍の重さの解がこのヒューリスティックで求まることを示す。
- 1998-09-18
著者
関連論文
- 連結頂点被覆問題およびtree cover問題に対する2倍近似並列アルゴリズム
- 3-連結グラフに対する点被覆及び連結点被覆問題について
- 枝重み付きカクタスに対する発火系列問題の解法
- データ構造とアルゴリズム, 杉原厚吉(著), "データ構造とアルゴリズム",共立出版(2001-12);A5判, 定価(本体2,200円+税)
- d-claw freeグラフ上の独立集合問題に対する局所探索法について
- 2値重み集合被覆問題に対する貪欲法の改良について
- 重みが1と2の集合被覆問題に対する貪欲法の改良
- 劣モジュラ被覆問題の近似について
- いくつかのハイパーグラフ問題に対するPrimal-Dual近似アルゴリズムについて
- マトロイド的特性に関する点除去問題のプライマル・デュアル法による近似
- 最小コスト木状被覆問題の2倍近似アルゴリズム
- 重みつき集合充填問題に対する局所改善法について
- 集合多重被覆問題に対する貪欲法の改良
- 被覆容量/要求回数付き部分頂点被覆問題の2倍近似解法(アルゴリズム理論)
- A 2-Approximation Algorithm for Capacitated Partial Vertex Cover with Demands〔和文〕
- COMP2000-15 独立/連結な辺支配集合問題の近似可能性について
- 辺支配集合問題の2倍近似アルゴリズム
- 最小コスト辺支配集合問題の近似について (新しいパラダイムとしてのアルゴリズム工学)