About: 集合被覆問題

集合被覆問題（しゅうごうひふくもんだい）は、集合 U とその部分集合の族 S1,...,Sm が与えられたとき、U の要素を全てカバーするように部分集合の族から最小個数の部分集合を選ぶ問題。ここで、S1,...,Sm の和集合は、U に等しくなるものとする。 各部分集合 Si に対し重み wi が与えられ、選択した部分集合の重みの和を最小化する問題のことを指す場合もある。このような場合、重み付き集合被覆問題 と区別して呼ぶことも多い。全ての i について wi が等しいとき、重み無し集合被覆問題と等価なので、重み無し集合被覆問題は、重み付き集合被覆問題の特殊な場合とも言える。 重み無し・重み付きを問わず、この問題はNP困難であることが知られている。そのため、集合に制約を加えた問題や近似アルゴリズムの研究がさかんである。