Approximating multiobjective knapsack problems

被引:71
作者
Erlebach, T [1 ]
Kellerer, H
Pferschy, U
机构
[1] Swiss Fed Inst Technol, Comp Engn & Networks Lab, CH-8092 Zurich, Switzerland
[2] Graz Univ, Dept Stat & Operat Res, A-8010 Graz, Austria
关键词
knapsack problem; multiobjective optimization; approximation scheme;
D O I
10.1287/mnsc.48.12.1603.445
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
For multiobjective optimization problems, it is meaningful to compute a set of solutions covering all possible trade-offs between the different objectives. The multiobjective knapsack problem is a generalization of the classical knapsack problem in which each item has several profit values. For this problem, efficient algorithms for computing a provably good approximation to the set of all nondominated feasible solutions, the Pareto frontier, are studied. For the multiobjective one-dimensional knapsack problem, a practical fully polynomial time approximation scheme (FPTAS) is derived. It is based on a new approach to the single objective knapsack problem using a partition of the profit space into intervals of exponentially increasing length. For the multiobjective m-dimensional knapsack problem, the first known polynomial-time approximation scheme (PTAS), based on linear programming, is presented.
引用
收藏
页码:1603 / 1612
页数:10
相关论文
共 17 条
[1]  
[Anonymous], 1990, KNAPSACK PROBLEMS
[2]   A survey and annotated bibliography of multiobjective combinatorial optimization [J].
Ehrgott M. ;
Gandibleux X. .
OR-Spektrum, 2000, 22 (4) :425-460
[3]  
Ehrgott M., 2000, Multicriteria Optimization
[4]   APPROXIMATION ALGORITHMS FOR THE M-DIMENSIONAL 0-1 KNAPSACK-PROBLEM - WORST-CASE AND PROBABILISTIC ANALYSES [J].
FRIEZE, AM ;
CLARKE, MRB .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 15 (01) :100-109
[5]   FAST APPROXIMATION ALGORITHMS FOR KNAPSACK AND SUM OF SUBSET PROBLEMS [J].
IBARRA, OH ;
KIM, CE .
JOURNAL OF THE ACM, 1975, 22 (04) :463-468
[6]   A new fully polynomial time approximation scheme for the knapsack problem [J].
Kellerer, H ;
Pferschy, U .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 1999, 3 (01) :59-71
[7]  
KELLERER H, 2002, IN PRESS J COMBIN OP
[8]  
Khachiyan L. G., 1980, USSR Computational Mathematics and Mathematical Physics, V20, P53, DOI [10.1016/0041-5553(80)90061-0, DOI 10.1016/0041-5553(80)90061-0]
[9]  
Klamroth K, 2000, NAV RES LOG, V47, P57, DOI 10.1002/(SICI)1520-6750(200002)47:1<57::AID-NAV4>3.0.CO
[10]  
2-4