集合しゅうごう被覆ひふく問題もんだい

集合しゅうごう被覆ひふく問題もんだい（しゅうごうひふくもんだい）は、集合しゅうごう 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]