集合被覆問題

【しゅうごうひふくもんだい (set covering problem)】

集合$M=\{e_{1},\cdots ,e_{m}\}\,$の部分集合$S_{j}(j=1,\cdots ,n)\,$に対してコスト$c_{j}\,$が与えられている. このとき和集合が$M\,$となるような構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S_j\,} の組合せの中で対応するコストの総和が最小となるものを求める問題. さらに, 選ばれた 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S_j\,} が互いに重ならないという制約を加える場合を集合分割問題と呼ぶ. 携帯電話の受送信センターの配置問題など応用例は豊富である.