Online Knapsack Revisited

Lukasz Jez

Abstract

(joint work with M. Cygan)

In a natural online variant of the (Max) Knapsack Problem, we are given one item after another and after each item have to irrevocably decide whether we place it in the knapsack or not, without knowing the future items.

Formulated this way, the problem admits no constant-competitive algorithm. To get around this problem, several approaches, including stochastic ones, have been proposed. We focus on one by Iwama et al., which allows the algorithm to remove items from the knapsack (and lose them forever).

The setting is as follows: an algorithm is to pack items, of arbitrary sizes and profits, in k knapsacks (bins) without exceeding the capacity of any bin. We study two objective functions: the sum and the maximum of profits over all bins. The first of these was partially considered in the dual bin packing problem, whereas the second is the one studied by Iwama et al. for a restricted variant of the problem.