2026-07-23T03:22:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:869 2024-03-06T11:07:06Z ddc:004 open_access

Adaptive Analysis of On-line Algorithms Dorrigiv, Reza Lopez-Ortiz, Alejandro On-line algorithms paging adaptive/cooperative analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Reza Dorrigiv and Alejandro Lopez-Ortiz 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06421.4 urn:nbn:de:0030-drops-8696 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.4 eng https://creativecommons.org/licenses/by/4.0/legalcode