License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06421.4
URN: urn:nbn:de:0030-drops-8696
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/869/
Go to the corresponding Portal

Dorrigiv, Reza ; Lopez-Ortiz, Alejandro

Adaptive Analysis of On-line Algorithms

pdf-format:
06421.LopezOrtizAlejandro.Paper.869.pdf (0.2 MB)

Abstract

On-line algorithms are usually analyzed using competitive analysis, in which the performance
of on-line algorithm on a sequence is normalized by the performance of the optimal on-line
algorithm on that sequence. In this paper we introduce adaptive/cooperative analysis as an
alternative general framework for the analysis of on-line algorithms. This model gives promising
results when applied to two well known on-line problems, paging and list update. The idea is
to normalize the performance of an on-line algorithm by a measure other than the performance
of the on-line optimal algorithm OPT. We show that in many instances the perform of OPT
on a sequence is a coarse approximation of the difficulty or complexity of a given input. Using
a finer, more natural measure we can separate paging and list update algorithms which were
otherwise undistinguishable under the classical model. This createas a performance hierarchy of
algorithms which better reflects the intuitive relative strengths between them. Lastly, we show
that, surprisingly, certain randomized algorithms which are superior to MTF in the classical
model are not so in the adaptive case. This confirms that the ability of the on-line adaptive
algorithm to ignore pathological worst cases can lead to algorithms that are more efficient in
practice.

BibTeX - Entry

@InProceedings{dorrigiv_et_al:DagSemProc.06421.4,
  author =	{Dorrigiv, Reza and Lopez-Ortiz, Alejandro},
  title =	{{Adaptive Analysis of On-line Algorithms}},
  booktitle =	{Robot Navigation},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/869},
  URN =		{urn:nbn:de:0030-drops-8696},
  doi =		{10.4230/DagSemProc.06421.4},
  annote =	{Keywords: On-line algorithms, paging, adaptive/cooperative analysis}
}

Keywords: On-line algorithms, paging, adaptive/cooperative analysis
Collection: 06421 - Robot Navigation
Issue Date: 2007
Date of publication: 07.02.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI