An O(mn) Algorithm for Regular Set-Covering Problems
An O(mn) Algorithm for Regular Set-Covering Problems
复制标题
正则集覆盖问题的 O(mn) 算法
DOI：
10.1016/0304-3975(87)90131-9
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
A. Sassano
中科院分区：
文献类型：
--
作者：
P. Bertolazzi;A. Sassano
杂波 L 是基础集 E (L)={x 1,…, x n} 的 m 个子集的集合，其属性是，对于每对 A i, A j ϵ L，A i 既不包含也不包含 A j，L 的横截面是与 L 的每个成员相交的 E (L) 的子集。如果我们将每个元素 x j ϵ E (L) 与权重 c j 相关联，则找到具有最小权重的横截面的问题等效于以下集合覆盖问题 min {c T x| M L x⩾ 1 m, x j ϵ {0, 1}, j= 1,…, n} 其中 M L 是矩阵，其行是子集 A i ϵ L 的关联向量，1 m 表示具有 m 个的向量。如果存在变量 σ=(x 1,…, x n) 的排序，使得对于每个可行解 x 且 x i= 1, x j= 0, j< i，向量 x+ e j− e i 也是可行解，其中 e i 是第 i 个单位向量，则集合覆盖问题是常规问题。正则集合覆盖问题的矩阵 M 被称为正则矩阵。规则杂波是其关联矩阵是规则的任何杂波。在本文中，我们描述了规则杂波的一些属性，并提出了一种算法，该算法以 O (mn) 步生成规则杂波 L 的所有最小横截面，并产生具有最小权重的横截面。
A clutter L is a collection of m subsets of a ground set E (L)={x 1,…, x n} with the property that, for every pair A i, A j ϵ L, A i is neither contained nor contains A j, A transversal of L is a subset of E (L) intersecting every member of L. If we associate with each element x j ϵ E (L) a weight c j, the problem of finding a transversal having minimum weight is equivalent to the following set-covering problem min {c T x| M L x⩾ 1 m, x j ϵ {0, 1}, j= 1,…, n} where M L is the matrix whose rows are the incidence vectors of the subsets A i ϵ L and 1 m denotes the vector with m ones. A set-covering problem is regular if there exists an ordering of the variables σ=(x 1,…, x n) such that, for every feasible solution x with x i= 1, x j= 0, j< i, the vector x+ e j− e i is also a feasible solution, where e i is the ith unit vector. The matrix M of a regular set-covering problem is said to be regular. A regular clutter is any clutter whose incidence matrix is regular. In this paper we describe some properties of regular clutters and propose an algorithm which, in O (mn) steps, generates all the minimal transversals of a regular clutter L and produces the transversal having minimum weight.