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 ra tios. However, these algorithms can obtain very low profit with high probab ility. We investigate the question of devising for these problems on-line c ompetitive algorithms that also guarantee a good solution with good probabi lity. We give a new family of randomized algorithms with asymptotically optimal c ompetitive ratios and good probability to get a profit close to the expecta tion. 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 know ledge, this is the rst study of the relationship between the tail distribut ion and the competitive ratio of randomized on-line benefit algorithms.