An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

In this note we study packing or covering integer programs with at most k constraints, which are also known as k-dimensional knapsack problems. For any integer k > 0 and real epsilon > 0, we observe there is a polynomial-sized LP for the k-dimensional knapsack problem with integrality gap at most 1+epsilon. The variables may be unbounded or have arbitrary upper bounds. In the packing case, we can also remove the dependence of the LP on the cost-function, yielding a polyhedral approximation of the integer hull. This generalizes a recent result of Bienstock on the classical knapsack problem.

No associations

LandOfFree

Say what you really think

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

Rating

An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack 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 An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-477802

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