2019/02/22 by Chekuri, Chandra, Quanrud, Kent, Torres, Manuel R.
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1902.08698
We consider approximation algorithms for packing integer programs (PIPs) of the form max\⟨ c, x⟩ : Ax ≤ b, x ∈ \0,1\n\ where c, A, and b are nonnegative. We let W = mini,j bi / Ai,j denote the width of A which is at least 1. Previous work by Bansal et al. \citebansal-sparse obtained an Ω(\frac1Δ01/\lfloor W \rfloor)-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) \citecq,chs-16 we show that simple algorithms based on randomized rounding followed by alteration, similar to those of Bansal et al. \citebansal-sparse (but with a twist), yield approximation ratios for PIPs based on Δ1. First, following an integrality gap example from \citebansal-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 = Ω((log (Δ1/ε))/(ε2)).