Greedy Set-Cover Algorithms
Greedy Set-Cover Algorithms
复制标题
贪心集合覆盖算法
DOI：
10.1007/978-1-4939-2864-4_175
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
N. Young
中科院分区：
文献类型：
--
作者：
N. Young
给定论域U上的集合S，集合覆盖C⊆S是并为U的集合的子集合。集覆盖问题是给定S的一个最小基数集覆盖问题。在加权集覆盖问题中，对每个集S∈S也指定一个权重ws≥0，目标是找到一个集合覆盖C的最小总权∑S∈C ws.加权集合覆盖是最小化受子模约束的线性函数的特例，定义如下。给定一个S对象集合，对于每个对象S，一个非负权重ws，和一个非减子模函数f：2 S→R，目标是找到一个子集C⊆S，使得f(C)=f(S)最小化∑S∈Cws。(取f(C)=|∪S∈C S|给出加权集覆盖。)
Given a collection S of sets over a universe U , a set cover C ⊆ S is a subcollection of the sets whose union is U . The set-cover problem is, given S, to find a minimum-cardinality set cover. In the weighted set-cover problem, for each set s ∈ S a weight ws ≥ 0 is also specified, and the goal is to find a set cover C of minimum total weight ∑ s∈C ws. Weighted set cover is a special case of minimizing a linear function subject to a submodular constraint, defined as follows. Given a collection S of objects, for each object s a non-negative weight ws, and a non-decreasing submodular function f : 2 S → R, the goal is to find a subcollection C ⊆ S such that f(C) = f(S) minimizing ∑ s∈C ws. (Taking f(C) = | ∪s∈C s| gives weighted set cover.)