集合カバー問題

出典: ORWiki

【しゅうごうかばーもんだい (set covering problem)】

集合 $M=\{ e_1, \cdots, e_m\}\,$ の部分集合 $S_j (j=1, \cdots , n)\,$ に対してコスト $c_j\,$ が与えられている. このとき和集合が $M\,$ となるような $S_j\,$ の組合せの中で対応するコストの総和が最小となるものを求める問題を集合被覆問題,あるいは集合カバー問題という. さらに, 選ばれた $S_j\,$ が互いに重ならないという制約を加える場合を集合分割問題と呼ぶ. 携帯電話の受送信センターの配置問題など応用例は豊富である.