# Item

ITEM ACTIONSEXPORT

Released

Report

#### Randomized on-line call control revisited

##### Fulltext (public)

MPI-I-97-1-022.pdf

(Any fulltext), 139KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Leonardi, S., & Marchetti-Spaccamela, A. P.(1997). *Randomized
on-line call control revisited* (MPI-I-97-1-023). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-9D6E-8

##### Abstract

We consider the on-line problem of call admission and routing on
trees and meshes. Previous work considered randomized algorithms
and analyzed the {\em 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 see
this work as a first step towards understanding
how well can the profit of an competitively-optimal randomized on-line
algorithm be concentrated around its expectation.