A stochastic algorithm for online bipartite resource allocation problems

Two main approaches have been proposed to address such online problems, depending on the assumptions made about the input sequence: one is trying to guarantee a performance against a worst case scenario (sometimes called the adversarial model); the other one, based on specific probabilistic assumptions about the input, is concerned with expected performance guarantee. However, combining the strengths of these two approaches could potentially outperform both in some settings. In this paper we propose such a practical method which goes beyond the adversarial model but requires only a limited amount of information about the future. We provide extensive computational results which demonstrate settings under which the performance of the proposed algorithm becomes attractive.