2013/11/18 by Daniel Bienstock, Bienstock, Daniel, Jay Sethuraman +3 · 2 citations
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1311.4563
openalex publication_date 2013/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the incremental knapsack problem (\IK), we are given a knapsack whose capacity grows weakly as a function of time. There is a time horizon of T periods and the capacity of the knapsack is Bt in period t for t = 1, …, T. We are also given a set S of N items to be placed in the knapsack. Item i has a value of vi and a weight of wi that is independent of the time period. At any time period t, the sum of the weights of the items in the knapsack cannot exceed the knapsack capacity Bt. Moreover, once an item is placed in the knapsack, it cannot be removed from the knapsack at a later time period. We seek to maximize the sum of (discounted) knapsack values over time subject to the capacity constraints. We first give a constant factor approximation algorithm for \IK, under mild restrictions on the growth rate of Bt (the constant factor depends on the growth rate). We then give a PTAS for \IIK, the special case of \IK with no discounting, when T = O(√(log N)).