ℓ_1-sparsity Approximation Bounds for Packing Integer Programs
share
We consider approximation algorithms for packing integer programs (PIPs) of the form {〈 c, x〉 : Ax < b, x ∈{0,1}^n} where c, A, and b are nonnegative. We let W = _i,j b_i / A_i,j denote the width of A which is at least 1. Previous work by Bansal et al. bansal-sparse obtained an Ω(1/Δ_0^1/ W )-approximation ratio where Δ_0 is the maximum number of nonzeroes in any column of A (in other words the ℓ_0-column sparsity of A). They raised the question of obtaining approximation ratios based on the ℓ_1-column sparsity of A (denoted by Δ_1) which can be much smaller than Δ_0. Motivated by recent work on covering integer programs (CIPs) cq,chs-16 we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. bansal-sparse (but with a twist), yield approximation ratios for PIPs based on Δ_1. First, following an integrality gap example from bansal-sparse, we observe that the case of W=1 is as hard as maximum independent set even when Δ_1 < 2. In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width W = 1 + ϵ where ϵ∈ (0,1], we obtain an Ω(ϵ^2/Δ_1)-approximation. In the large width regime, when W > 2, we obtain an Ω((1/1 + Δ_1/W)^1/(W-1))-approximation. We also obtain a (1-ϵ)-approximation when W = Ω( (Δ_1/ϵ)/ϵ^2).
READ FULL TEXT