Incremental knapsack problems

Yuri Faenza (Columbia University)

Abstract: In this talk, we propose and study discrete, multi-period extensions of classical packing problems, a fundamental class of models in combinatorial optimization. Those extensions fall under the general name of incremental packing problems. We will mostly focus on incremental versions of the classical knapsack. In such models, we are given an added time component and weakly increasing capacities for each time, as to mimic the increase in available resources. Items can be inserted at any time, but once an item is inserted, it cannot be removed in future times. The goal is to maximize some item-dependent, and possibly also time-dependent, objective function under such constraints. We will present algorithms that perform well in theory and/or in practice for incremental knapsack problems and their extensions.
Based on joint work with Danny Segev (Tel Aviv) and Lingyi Zhang (Columbia-> Uber).