摘要
给出了集合覆盖问题的一种随机近似算法。给定E={e1,e2,…,en}的子集的集合S和S中每个子集的权值,带权的集合覆盖问题是从S中选择费用和最小的子集使得其并集覆盖E。对E中每一个未被覆盖的元素,以某一精心设计的概率分布选择包含该元素的子集,直到E中所有元素均被覆盖,算法结束。该算法求出的覆盖的费用的期望值不超过B.opt,其中opt为最优覆盖的费用,B=maxe∈E{|L(e)|},L(e)={s|e∈s,s∈S}。算法时间复杂度为O(n),其中n为E的元素数目。
A randomized approximation algorithm for the set cover problem was proposed. Given a collection S of subsets of E= {el ,e2……en} with weights on the subsets, the goal of the weighted set cover problem is to cover all the elements of E by picking a subset with the minimum total cost from S . For each uncovered element of the set E, a subset which contains the element was chosen with a certain elaborately designed probability distribution. The algorithm will not terminate until all the elements have been covered. The proposed algorithm computes a cover whose expected cost is at most B. opt where opt is the cost of some optimal cover for the problem, where B=max{|L(e)|} and eE E L(e)={s|e∈s,s∈S}. The running time of the algorithm is O(n) wheren is the cardinalityof E.
出处
《吉林大学学报(工学版)》
EI
CAS
CSCD
北大核心
2007年第2期429-432,共4页
Journal of Jilin University:Engineering and Technology Edition
基金
国家自然科学基金资助项目(60573024)
关键词
计算机应用
随机算法
近似算法
集合覆盖
computer application
randomized algorithm
approximation algorithm
set cover