Size-stochastic Knapsack Online Contention Resolution Schemes
share
Online contention resolution schemes (OCRSs) are effective rounding techniques for online stochastic combinatorial optimization problems. These schemes randomly and sequentially round a fractional solution to a relaxed problem that can be formulated in advance. We propose OCRSs for online stochastic generalized assignment problems. In the OCRSs problem, sequentially arriving items are packed into a single knapsack, and their sizes are revealed only after insertion. The goal of the problem is to maximize the acceptance probability, which is the smallest probability among the items of being placed in the knapsack. Since the item sizes are unknown beforehand, a capacity overflow may occur. We consider two distinct settings: the hard constraint, where items that cause overflow are rejected, and the soft constraint, where such items are accepted. Under the hard constraint setting, we present an algorithm with an acceptance probability of 1/3, and we also prove that no algorithm can achieve an acceptance probability greater than 3/7. Under the soft constraint setting, we propose an algorithm with an acceptance probability of 1/2, and we show that this is best possible.
READ FULL TEXT