Randomized approximation of bounded multicovering problems

被引：0
作者：
D. Peleg
G. Schechtman
A. Wool
机构：
[1] The Weizmann Institute,Department of Applied Mathematics and Computer Science
[2] The Weizmann Institute,Department of Theoretical Mathematics
[3] Bell Laboratories,undefined
来源：
Algorithmica | 1997年 / 18卷
关键词：
Integer linear programs; Randomized rounding; Set cover; Approximation algorithms;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1}n that minimizes ∑jxj subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1.
引用
收藏
页码：44 / 66
页数：22
相关论文
共 27 条
[1]  
Bar-Yehuda R.(1985)A local-ratio theorem for approximating the weighted vertex cover problem Ann. Discrete Math. 25 27-46
[2]  
Even S.(1993)How to allocate network centers J. Algorithms 15 385-415
[3]  
Bar-Ilan J.(1952)A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations Ann. Math. Statist. 23 493-509
[4]  
Kortsarz G.(1979)A greedy heuristic for the set-covering problem Math. Oper. Res. 4 233-235
[5]  
Peleg D.(1982)Worst case analysis of greedy heuristics for integer programming with nonnegative data Math. Oper. Res. 7 515-531
[6]  
Chernoff H.(1986)A fast approximation algorithm for the multicovering problem Discrete Appl. Math. 15 35-40
[7]  
Chvatal V.(1982)Approximation algorithms for the set covering and vertex cover problems SIAM J. Comput. 11 555-556
[8]  
Dobson G.(1983)Efficient bounds for the stable set, vertex cover, and set packing problems Discrete Appl. Math. 6 243-254
[9]  
Hall N. G.(1983)On the fractional solution to the set covering problem SIAM J. Algebraic Discrete Methods 4 221-222
[10]  
Hochbaum D. S.(1986)A unified approach to approximation algorithms for bottleneck problems J. Assoc. Comput. Mach. 33 533-550
123