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

Friday, February 17, 2023 12:00 pm - 12:00 pm EST (GMT -05:00)

Title: (1+epsilon)-approximating knapsack polytopes

Speaker: Noah Weninger
Institution: University of Waterloo
Location: MC 6029

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