Abstract
We present an algorithmic technique for online algorithms on instances that are defined by an adversary but come in random order. In particular, this includes linear packing problems that are defined as follows. The variables of a packing linear program arrive one after the other. We get to know a variable's contributions to objective function and constraints only when it arrives. At this point in time, we have to set the respective variable?s value immediately and irrevocably. One example of such a problem is online knapsack: Objects of different profits and weights arrive one after the other. We have to choose a subset of these objects so as to maximize the profit while keeping the overall weight below a given bound. With random arrival order, it is possible to get close to the optimal offline solution. Using our approach, we obtain a simple algorithm achieving the optimal competitive ratio.