Technical Note—An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem
针对容量随时间扩张的增量背包问题，本文提出了首个多项式时间近似方案，通过近似动态规划等技术给出最强性能保证，对运筹学和算法设计研究者有参考价值。
Integer packing problems have traditionally been some of the most fundamental and well-studied computational questions in discrete optimization. The paper by Aouad and Segev studies the incremental knapsack problem, where one wishes to sequentially pack items into a knapsack whose capacity expands over a finite planning horizon, with the objective of maximizing time-averaged profits. Although various approximation algorithms were developed under mitigating structural assumptions, obtaining nontrivial performance guarantees for this problem in its utmost generality has remained an open question thus far. The authors devise the first polynomial-time approximation scheme for general instances of the incremental knapsack problem, which is the strongest guarantee possible given existing hardness results. Their approach synthesizes various techniques related to approximate dynamic programming, including problem decompositions, counting arguments, and efficient rounding methods, which may be of broader interest.