On the advice complexity of the knapsack problem

Sander Verdonschot

Advice complexity is a recent addition to the complexity landscape. It allows algorithms to ask a small number of questions from an oracle. This is usually applied to online algorithms, where it captures an amount of information about future events, as the oracle has access to the full input. In this talk, I will focus on one particular online problem: Unweighted (or Simple) Knapsack. If we don't allow any advice, there is no deterministic algorithm that can even approximate the best offline solution. But allowing even a single bit of advice gives us an algorithm that is guaranteed to be within a factor of 2 of the optimal solution.