Loading...
Please wait, while we are loading the content...
Similar Documents
On-line randomized call-control revisited (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Leonardi, Stefano Marchetti-Spaccamela, Alberto |
| Description | In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms ALESSIO PRESCIUTTI † , AND ADI ROSÉN ‡ 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 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 first study of the relationshipbetween the tail distribution and the competitive ratio of randomized on-line benefit algorithms. |
| File Format | |
| Language | English |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Randomized Algorithm Previous Work Alessio Presciutti Randomized On-line Benefit Algorithm First Study Competitive Algorithm On-line Algorithm Good Probability Good Solution Competitive Ratio Tail Distribution New Family Optimal Competitive Ratio On-line Call Admission High Probability Low Profit Constant Factor Adi Ro Abstract Profit Close |
| Content Type | Text |
| Resource Type | Article |
