Approximate formulations for 0-1 knapsack sets

Daniel Bienstock (danocolumbia.edu)

Abstract: A classical theorem in Combinatorial Optimization proves the existence of fully polynomial- time approximation schemes for the knapsack problem. In a recent paper, Van Vyve and Wolsey ask whether for each 0 < epsilon ≤ 1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables and/or 1/epsilon , whose value is at most (1+ epsilon) times the value of the integer program. times the value of the integer program. In this note we partially answer this question in the affirmative, using techniques similar to those in Bienstock and Zuckerberg, SIOPT, 2006.

Keywords: Integer programming, combinatorial optimization

Category 1: Integer Programming

Category 2: Combinatorial Optimization

Citation: CORC Report TR-2006-03, Columbia University, September, 2006

Download: [PDF]

Entry Submitted: 10/23/2006
Entry Accepted: 10/23/2006
Entry Last Modified: 11/14/2006

Modify/Update this entry