On-line randomized call control revisited

Citation
S. Leonardi et al., On-line randomized call control revisited, SIAM J COMP, 31(1), 2001, pp. 86-112
Citations number
20
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
1
Year of publication
2001
Pages
86 - 112
Database
ISI
SICI code
0097-5397(20010729)31:1<86:ORCCR>2.0.ZU;2-V
Abstract
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.