On-line randomized call control revisited

We consider the problem of on-line call admission and routing on trees and meshes. Previous work gave randomized on-line algorithms for these problems and proved that they have optimal ( up to constant factors) competitive ratios. However, these algorithms can obtain very low profit with high probability. We investigate the question of devising for these problems on-line competitive algorithms that also guarantee a good solution with good probability. We give a new family of randomized algorithms with asymptotically optimal competitive ratios and good probability to get a profit close to the expectation. We complement these results by providing bounds on the probability of any optimally competitive randomized on-line algorithm for the problems we consider to get a profit close to the expectation. To the best of our knowledge, this is the rst study of the relationship between the tail distribution and the competitive ratio of randomized on-line benefit algorithms.