Approximate formulations for 0-1 knapsack sets

被引：30
作者：
Bienstock, Daniel [1 ]
机构：
[1] Columbia Univ, Dept IEOR, New York, NY 10027 USA
来源：
OPERATIONS RESEARCH LETTERS | 2008年 / 36卷 / 03期
关键词：
integer programming; approximation algorithms; lift-and-project;
D O I：
10.1016/j.orl.2007.09.003
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We show that for each 0 < epsilon <= 1 there exists an extended formulation for the knapsack problem, of size polynomial in the number of variables, whose value is at most (1 + epsilon) times the value of the integer program. (C) 2007 Elsevier B.V. All rights reserved.
引用
收藏
页码：317 / 320
页数：4
相关论文
共 50 条
12345