重み無し集合被覆問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/21 00:19 UTC 版)
「集合被覆問題」の記事における「重み無し集合被覆問題」の解説
貪欲法によって、近似度 ln|U|+1 の解を得ることができることが知られている。特に、各部分集合の要素の数が k 以内であることがわかっているとき (k-set cover problem)、調和級数 Hk (= 1+1/2+…+1/k) を用いると、近似度 Hk + 1 (≦ ln k + 1) になることが知られている。逆に、NP⊆QP が成り立たないとき、任意のε>0について、近似度 (1-ε) ln |U| の多項式時間アルゴリズムが存在しないことも示されている。 k-set cover problem については、k=2 のとき、最大マッチング問題の解法を応用することで容易に最適解が求められることが知られているが、k>2 の場合については、MAX SNP-hardであることが知られている。k>2 の場合について、Duh と Fürer は、1997年、k-set cover problem に対して、Hk - 1/2 近似アルゴリズムを与えた。 また、最も高頻度に現れる集合の要素の頻度を f とおくとき、近似度 f の近似アルゴリズムも存在することが知られている。
※この「重み無し集合被覆問題」の解説は、「集合被覆問題」の解説の一部です。
「重み無し集合被覆問題」を含む「集合被覆問題」の記事については、「集合被覆問題」の概要を参照ください。
ウィキペディア小見出し辞書の「重み無し集合被覆問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 重み無し集合被覆問題のページへのリンク
