|
|||||
|
|
Approximate formulations for 0-1 knapsack sets |
|
| Authors: | Daniel Bienstock |
| Institution: | Department of IEOR, Columbia University, New York, NY 10027, USA |
| Abstract: | We show that for each 0<?≤1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables, whose value is at most (1+?) times the value of the integer program. |
| Keywords: | Integer programming Approximation algorithms Lift-and-project |
| 本文献已被 ScienceDirect 等数据库收录！ | |