  


Approximate formulations for 01 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 TR200603, Columbia University, September, 2006 Download: [PDF] Entry Submitted: 10/23/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  