On the partitioning algorithm

We consider the deterministic and the randomized paging problem. We show the close connection between the partitioning algorithm of McGeoch and Sleator and the OPT graph of the problem via a natural framework. This allows us to prove some important properties of the "deterministic" partiti...

Full description

Saved in:
Bibliographic Details
Main Author: Csaba Béla
Corporate Author: Conference for PhD Students in Computer Science (1.) (1998) (Szeged)
Format: Article
Published: 1999
Series:Acta cybernetica 14 No. 2
Kulcsszavak:Számítástechnika, Kibernetika, Algoritmus
Subjects:
Online Access:http://acta.bibl.u-szeged.hu/12622
Description
Summary:We consider the deterministic and the randomized paging problem. We show the close connection between the partitioning algorithm of McGeoch and Sleator and the OPT graph of the problem via a natural framework. This allows us to prove some important properties of the "deterministic" partitioning algorithm. As a consequence of these we prove, that it is a kcompetitive deterministic on-line algorithm. Besides, we show an application of the OPT graph for a special case of the fc-server problem.
Physical Description:217-227
ISSN:0324-721X