Approximating bounded 0-1 integer linear programs

The problem of finding approximate solutions for a subclass of 0-1 integer linear programming denoted by I L P( k,p) is considered. The problem involves finding X ∈ {0,1}ⁿ that minimizes Σ_jX _j subject to the constraint AX⩾p.1 _m, where A is a 0-1 m×n matrix with at most k 1´s per row, and 1_m is the all-1 m-vector. This is a MAX-SNP-hard problem, and special cases include, for example, the bounded set cover problem when p=1, and the vertex cover problem when k=2 and p=1. Several deterministic approximation algorithms are presented, all with approximation ratios of k-p+1, which is constant when the difference k-p is bounded. This naturally applies in the common case when both k and p are bounded, and is asymptotically better than the 1n(mp) ratio guaranteed by the greedy heuristic. A randomized approximation algorithm is also given, with approximation ratio (k-p+1) (1-( ^c/_m)¹(k-p+1)/) for a small constant c>0. The analysis of this algorithm relies on the use of a new and surprising bound on the sum of independent Bernoulli random variables, that is of interest in its own right