Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Randomized on-line call control revisited

Leonardi, Stefano Alberto and Marchetti-Spaccamela, Alessio Presciutti

MPI-I-97-1-023. October 1997, 19 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-97-1-023.ps206 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Leonardi, Stefano Alberto and Marchetti-Spaccamela, Alessio Presciutti},
  TITLE = {Randomized on-line call control revisited},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-023},
  MONTH = {October},
  YEAR = {1997},
  ISSN = {0946-011X},