On-line randomized call control revisited

We consider the on-line problem of call admission and routing on trees and meshes. Previous work considered randomized algorithms and analyzed the competitive ratio of the algorithms. However, these previous algorithms could obtain very low profit with high probability. We investigate the question if it is possible to devise on-line competitive algorithms for these problems that would guarantee a 'good' solution with 'good' probability. We give a new family of randomized algorithms with provably optimal (up to constant factors) competitive ratios, and provably good probability to get a profit close to the expectation. We also give lower bounds that show bounds on how high the probability of such algorithms, to get a profit close to the expectation, can be. We also hope that this work could serve as a first step towards understanding how well can the profit of an competitively-optimal randomized on-line algorithm be concentrated around its expectation. (orig.)Available from TIB Hannover: RR 1912(97-1-023) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman