On k-Column Sparse Packing Programs

Abstract

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 $k^2\cdot 2^k$ and $O(k^2)$. 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 $\Omega (k/\log k)$-hard to approximate. 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.

19 pages, v3: additional details

References in corpus (1)

• On k-Column Sparse Packing Programs

Cited by in corpus (5)

• Precoder Design for Physical Layer Multicasting
• Distributed algorithms for covering, packing and maximum weighted matching
• On k-Column Sparse Packing Programs
• Iterative Packing for Demand and Hypergraph Matching
• Generalized Hypergraph Matching via Iterated Packing and Local Ratio