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 条
  • [1] Reoptimizing the 0-1 knapsack problem
    Archetti, Claudia
    Bertazzi, Luca
    Speranza, M. Grazia
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (17) : 1879 - 1887
  • [2] Separation algorithms for 0-1 knapsack polytopes
    Konstantinos Kaparis
    Adam N. Letchford
    Mathematical Programming, 2010, 124 : 69 - 91
  • [3] The 0-1 knapsack problem with fuzzy data
    Adam Kasperski
    Michał Kulej
    Fuzzy Optimization and Decision Making, 2007, 6 : 163 - 172
  • [4] Separation algorithms for 0-1 knapsack polytopes
    Kaparis, Konstantinos
    Letchford, Adam N.
    MATHEMATICAL PROGRAMMING, 2010, 124 (1-2) : 69 - 91
  • [5] The 0-1 knapsack problem with fuzzy data
    Kasperski, Adam
    Kulej, Michal
    FUZZY OPTIMIZATION AND DECISION MAKING, 2007, 6 (02) : 163 - 172
  • [6] A core approach to the 0-1 equality knapsack problem
    Volgenant, A
    Marsman, S
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1998, 49 (01) : 86 - 92
  • [7] On characterizing tighter formulations for 0-1 programs
    Escudero, LF
    Munoz, S
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1998, 106 (01) : 172 - 176
  • [8] A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem
    Yoon, Yourim
    Kim, Yong-Hyuk
    Moon, Byung-Ro
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 218 (02) : 366 - 376
  • [9] AN IMPROVED HEURISTIC FOR MULTIDIMENSIONAL 0-1 KNAPSACK-PROBLEMS
    VOLGENANT, A
    ZOON, JA
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (10) : 963 - 970
  • [10] On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra
    Miller, AJ
    Nemhauser, GL
    Savelsbergh, MWP
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 125 (02) : 298 - 315
12345