Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incured for transitioning from one state to another. In order to model such situations, Gupta et al. (ICALP 2014) and Eisenstat et al. (ICALP 2014) introduced a multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible. We focus on the multistage version of the Knapsack problem where we are given a time horizon t = 1, 2, . . . , T , and a sequence of knapsack instances I 1 , I 2 , . . . , I T , one for each time step, defined on a set of n objects. In every time step t we have to choose a feasible knapsack S t of I t , which gives a knapsack profit. To measure the stability/similarity of two consecutive solutions S t and S t+1 , we identify the objects for which the decision, to be picked or not, remains the same in S t and S t+1 , giving a transition profit. We are asked to produce a sequence of solutions S 1 , S 2 , . . . , S T so that the total knapsack profit plus the overall transition profit is maximized. We propose a PTAS for the Multistage Knapsack problem. This is the first approximation scheme for a combinatorial optimization problem in the considered multistage setting, and its existence contrasts with the inapproximability results for other combinatorial optimization problems that are even polynomial-time solvable in the static case (e.g.multistage Spanning Tree, or multistage Bipartite Perfect Matching). Then, we prove that there is no FPTAS for the problem even in the case where T = 2, unless P = N P . Furthermore, we give a pseudopolynomial time algorithm for the case where the number of steps is bounded by a fixed constant and we show that otherwise the problem remains NP-hard even in the case where all the weights, profits and capacities are 0 or 1.  ACM Subject Classification In a classical combinatorial optimization problem, given an instance of the problem we seek a feasible solution optimizing the objective function. However, in many systems the input may change over the time and the solution has to be adapted to the input changes. It is then necessary to determine a tradeoff between the optimality of the solutions in each time step and the stability/similarity of consecutive solutions. This is important since in many applications there is a significant transition cost for changing (parts of) a solution. Recently,
More recently, in REF , a multistage variant of the Knapsack problem has been studied.
Multistage Knapsack
ArXiv
ArXiv
Mathematics Computer Science