(1+epsilon)-approximating knapsack polytopes - Noah Weninger

Title: (1+epsilon)-approximating knapsack polytopes

Abstract: The 0-1 knapsack problem is a weakly NP-hard problem which admits a simple combinatorial FPTAS. In this talk, we will see that it is similarly possible to (1+epsilon)-approximate the knapsack polytope for any epsilon > 0 by using extended formulations, albeit with worse performance. I will present the result in the more general setting of approximating packing integer programs, which are also known as the multidimensional knapsack problem. This result is from the paper “An LP with Integrality Gap 1+epsilon for Multidimensional Knapsack” by David Pritchard