限定次数最大独立集合問題の近似について
スポンサーリンク
概要
- 論文の詳細を見る
最大独立集合問題は,組合せ最適化の基本的な問題である.この問題の最も重要な場合は,最大頂点次数が定数によって限定された場合であるが,その場合でさえ,この問題はNP完全であることが知られている.一方,この問題に対する自然な近似アルゴリズムはGreedyと呼ばれ,線形時間で実行できる.本論ではまず,このアルゴリズムの近似率を解析し,(Δ+2)/3近似率を示す.次に,この解析に基づいて,O(log^*n)時間の並列および分散アルゴリズムを設計する.最後に,独立集合アルゴリズムの近似率を改良するための一般的手法を紹介し,その手法を用いてO(Δ/loglogΔ)近似率を示す.これは始めてのo(Δ)近似率である.
- 一般社団法人情報処理学会の論文
- 1994-05-13