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.
Citation
CORC Report TR-2006-03, Columbia University, September, 2006