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
相关论文
共 14 条
[1]   A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].
BALAS, E ;
CERIA, S ;
CORNUEJOLS, G .
MATHEMATICAL PROGRAMMING, 1993, 58 (03) :295-324
[2]  
Balas E., 1975, NONLINEAR PROGRAMMIN, V2, P279, DOI DOI 10.1016/B978-0-12-468650-2.50015-8
[3]   Approximate fixed-rank closures of covering problems [J].
Bienstock, D ;
Zuckerberg, M .
MATHEMATICAL PROGRAMMING, 2006, 105 (01) :9-27
[4]   Subset algebra lift operators for 0-1 integer programming [J].
Bienstock, D ;
Zuckerberg, M .
SIAM JOURNAL ON OPTIMIZATION, 2004, 15 (01) :63-95
[5]  
Bienstock D., 2004, Discr. Optim, V1, P13, DOI [10.1016/j.disopt.2004.03.002, DOI 10.1016/J.DISOPT.2004.03.002]
[6]   On the matrix-cut rank of polyhedra [J].
Cook, W ;
Dash, S .
MATHEMATICS OF OPERATIONS RESEARCH, 2001, 26 (01) :19-30
[7]   When does the positive semidefiniteness constraint help in lifting procedures [J].
Goemans, MX ;
Tunçel, L .
MATHEMATICS OF OPERATIONS RESEARCH, 2001, 26 (04) :796-815
[8]   FAST APPROXIMATION ALGORITHMS FOR KNAPSACK AND SUM OF SUBSET PROBLEMS [J].
IBARRA, OH ;
KIM, CE .
JOURNAL OF THE ACM, 1975, 22 (04) :463-468
[9]  
LASSERRE JB, 2001, LECT NOTES COMPUTER, P293
[10]   A comparison of the Sherali-Adams, Lovasz-Schrijver, and Lasserre relaxations for 0-1 programming [J].
Laurent, M .
MATHEMATICS OF OPERATIONS RESEARCH, 2003, 28 (03) :470-496
12