TY - JOUR

T1 - Approximation schemes for the parametric knapsack problem

AU - Giudici, Alberto

AU - Halffmann, Pascal

AU - Ruzika, Stefan

AU - Thielen, Clemens

N1 - Publisher Copyright:
© 2016 Elsevier B.V.

PY - 2017/4/1

Y1 - 2017/4/1

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bicriteria optimization problems

KW - Parametric optimization problems

UR - http://www.scopus.com/inward/record.url?scp=85007008859&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2016.12.003

DO - 10.1016/j.ipl.2016.12.003

M3 - Article

AN - SCOPUS:85007008859

SN - 0020-0190

VL - 120

SP - 11

EP - 15

JO - Information Processing Letters

JF - Information Processing Letters

ER -