Computer Science – Data Structures and Algorithms
Scientific paper
2009-08-16
Computer Science
Data Structures and Algorithms
19 pages, v3: additional details
Scientific paper
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.
Bansal Nikhil
Korula Nitish
Nagarajan Viswanath
Srinivasan Aravind
No associations
LandOfFree
On k-Column Sparse Packing Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On k-Column Sparse Packing Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On k-Column Sparse Packing Programs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-704811