Approximation schemes for the parametric knapsack problem

被引:15
作者
Giudici, Alberto [1 ]
Halffmann, Pascal [2 ]
Ruzika, Stefan [2 ]
Thielen, Clemens [3 ]
机构
[1] Erasmus Univ, Rotterdam Sch Management, NL-3000 DR Rotterdam, Netherlands
[2] Univ Koblenz Landau, Math Inst, Campus Koblenz, D-56070 Koblenz, Germany
[3] Univ Kaiserslautern, Dept Math, Paul Ehrlich Str 14, D-67663 Kaiserslautern, Germany
关键词
Parametric optimization problems; Approximation algorithms; Bicriteria optimization problems; MAXIMUM FLOW PROBLEM; ALGORITHMS; INTEGER;
D O I
10.1016/j.ipl.2016.12.003
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider the (linear) parametric 0-1 knapsack problem in which the profits of the items are affine-linear functions of a real-valued parameter and the task is to compute a solution for all values of the parameter. For this problem, it is known that the piecewise linear convex function mapping the parameter to the optimal objective value of the corresponding instance (called the optimal value function) can have exponentially many breakpoints (points of slope change), which implies that every optimal algorithm for the problem must output a number of solutions that is exponential in the number of items. We provide the first (parametric) polynomial time approximation scheme (PTAS) for the parametric 0-1 knapsack problem. Moreover, we exploit the connection between the parametric problem and the bicriteria problem in order to show that the parametric 0-1 knapsack problem admits a parametric FPTAS when the parameter is restricted to the positive real line and the slopes and intercepts of the affine-linear profit functions of the items are nonnegative. The method used to obtain this result applies to many linear parametric optimization problems and provides a general connection between bicriteria and linear parametric optimization problems. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:11 / 15
页数:5
相关论文
共 24 条
[1]  
[Anonymous], 1996, LECT NOTES COMPUTER
[2]  
[Anonymous], 2004, Knapsack Problems, DOI DOI 10.1007/978-3-540-24777-710
[3]   GENERALIZATION OF A THEOREM ON THE PARAMETRIC MAXIMUM FLOW PROBLEM [J].
ARAI, T ;
UENO, S ;
KAJITANI, Y .
DISCRETE APPLIED MATHEMATICS, 1993, 41 (01) :69-74
[4]  
Balaban I. J., 1995, Proceedings of the Eleventh Annual Symposium on Computational Geometry, P211, DOI 10.1145/220279.220302
[5]   Implementing an efficient fptas for the 0-1 multi-objective knapsack problem [J].
Bazgan, Cristina ;
Hugot, Hadrien ;
Vanderpooten, Daniel .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 198 (01) :47-56
[6]   THE INVERSE-PARAMETRIC KNAPSACK-PROBLEM [J].
BURKARD, RE ;
PFERSCHY, U .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 83 (02) :376-393
[7]  
Carstensen P. J., 1983, THESIS
[8]   COMPLEXITY OF SOME PARAMETRIC INTEGER AND NETWORK PROGRAMMING-PROBLEMS [J].
CARSTENSEN, PJ .
MATHEMATICAL PROGRAMMING, 1983, 26 (01) :64-75
[9]   REPORTING AND COUNTING SEGMENT INTERSECTIONS [J].
CHAZELLE, B .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1986, 32 (02) :156-182
[10]   Parametric solution for linear bicriteria knapsack models [J].
EbenChaime, M .
MANAGEMENT SCIENCE, 1996, 42 (11) :1565-1575