In this talk, I will present a simple 4.4-competitive algorithm for the online fractional knapsack problem under random arrivals. Despite being a classical combinatorial optimization problem, the fractional knapsack in the online setting has been touched upon only briefly in the theoretical computer science literature so far. In this problem, the algorithm sees items one by one, each with a weight and a value, according to a random permutation, and must decide irrevocably the fraction of the shown item in the final packing. The goal is to maximize the total profit respecting the knapsack capacity. For the integral version of the problem, Albers, Khan, and Ladewig gave a 6.65-competitive ratio by combining a secretary algorithm and a knapsack algorithm. We will see that a 4.4-competitive ratio can be achieved by extending the aforementioned knapsack algorithm to account for the possibility of packing items fractionally. On the hardness side, only an e-competitive lower bound is known, which stems from the secretary problem. I will conclude outlining potential future directions. Joint work with Andreas Karrenbauer.

ArXiv: https://arxiv.org/abs/2109.04428