On k-Column Sparse Packing Programs

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0


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.

No associations


Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.


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.

Rate now


Profile ID: LFWR-SCP-O-704811

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.