集合被覆問題

集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。

各部分集合 Si に対し重み wi が与えられ、選択した部分集合の重みの和を最小化する問題のことを指す場合もある。このような場合、重み付き集合被覆問題 と区別して呼ぶことも多い。全ての i について wi が等しいとき、重み無し集合被覆問題と等価なので、重み無し集合被覆問題は、重み付き集合被覆問題の特殊な場合とも言える。

重み無し・重み付きを問わず、この問題はNP困難であることが知られている。そのため、集合に制約を加えた問題や近似アルゴリズムの研究がさかんである。

重み無し集合被覆問題

貪欲法によって、近似度 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 の近似アルゴリズムも存在することが知られている。

重み付き集合被覆問題

重み無しの場合と同様、貪欲法によって、近似度 ln|U|+1 の解を得ることができることが知られている。k-set cover problem に対しても、k=2 の場合は、最大マッチング問題の解法を応用することで容易に最適解が求められている。k>2 の場合については、Hassin と Levin が、2005年、Hk - (k-1)/(8k^9) 近似アルゴリズムの 存在を示した。

外部リンク

• MINIMUM SET COVER [1]