On k-Column Sparse Packing Programs
Bansal, N Nikhil, Korula, N, Nagarajan, V, Srinivasan, A · 2009
We consider the class of packing integer programs (PIPs) that are column sparse, i.e. there is a specified upper bound k on the number of constraints that each variable appears in. We give an ek+o(k)approximation algorithm for k-column sparse PIPs, improving on recent results of k2 · 2k [14] and O(k2) [3, 5]. We also show that the integrality gap of our linear programming relaxation is at least 2k − 1; it is known that k-column sparse PIPs are Ω(k log k)-hard to approximate [8]. We also extend our result (at the loss of a small constant factor) to the more general case of maximizing a submodular objective over k-column sparse packing constraints.