Solve the online unweighted 0-1 knapsack problem efficiently

Question

I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must either place it into the bin (irrevocably) or ignore it. The objective is to maximize the number of items placed into the bin. (All inputs are positive integers.)

The offline algorithm is easy: place the items in the order $w_1\leq w_2\leq\cdots\leq w_n$ until the bin is full.

How can I solve this problem in an online fashion? My approach is to randomize the choices: once item $j$ appears, place it into the bin with probability $p_j$ and ignore it otherwise.

Answer 1

Well as you already noticed, or at least didn't mention, it is easy to see that there is no deterministic competitive Algorithm for your problem. (Counterexamples only need two items, and you can use the fact that the algorithm is deterministic.)

Your approach taking randomization actually isn't enough as some difficulties cannot be overcome by randomization. But there are a few relaxation models of your problem.

Some of those, and a few details to my answer can be found in the paper by Susanne Albers, Arindam Khan and Leon Ladewig named "Improved Online Algorithms for Knapsack and GAP in the Random Order Mode" (see section 1.1).