集合覆蓋問題研究.pdf

1、　　給定兩個集合E和S,元素的集合E和E的子集的集合S,求出S的子集C,使得C中所有集合的并等于E,同時使得|C|最小。這就是經(jīng)典的集合覆蓋問題(SCP)。它是NP-hard類的最優(yōu)化組合問題。對于NP-HARD類的問題,在P≠NP的假設(shè)下,是不存在多項(xiàng)式時間算法的,只能設(shè)計(jì)求解他們的近似算法或近似方案,或者對于問題條件進(jìn)行限制使得限制后的子問題是一個非NP-HARD類的問題。
　　集合覆蓋問題在實(shí)際應(yīng)用中有好多變型。若對于任意的

2、s∈S有一個權(quán)重w(s),并且同樣求c,使得sum from s∈C w(s)最小。問題就成為了帶有權(quán)重的集合覆蓋問題。若對于任意s∈S有一個限制正整數(shù)k(s),使得在s中的至多覆蓋k(s)個元素,問題就成為帶容量限制的集合覆蓋問題(CSCP),可以看出帶權(quán)重或帶容量限制的集合覆蓋問題至少和集合覆蓋問題一樣難。Lang和Yannakanis證明了集合覆蓋問題不存在c(lnn),c<1/4的近似算法,除非NP(？)Dtime(nPolyl

3、ogn)。Feige改進(jìn)了這個結(jié)果證明集合覆蓋問題不存在好于(1-ε)ln|s|近似比的多項(xiàng)式時間近似算法,ε>0,除非NP(？)Dtime(npolylogn),這是我們所知最新的反面結(jié)果。
　　帶容量限制的集合覆蓋問題是近年來集合覆蓋算法與復(fù)雜性研究的熱點(diǎn),在實(shí)踐中比一般集合覆蓋更具價值。集合覆蓋實(shí)用子問題的算法與復(fù)雜性多年來一直是計(jì)算機(jī)科學(xué)研究者攻克集合覆蓋問題的工作重點(diǎn)。Papadimitriou,Yannakakis證明