On the partitioning algorithm

Csaba Béla: On the partitioning algorithm. In: Acta cybernetica, (14) 2. pp. 217-227. (1999)

[thumbnail of cybernetica_014_numb_002_217-227.pdf]
Cikk, tanulmány, mű

Download (1MB) | Preview


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.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1999
Volume: 14
Number: 2
ISSN: 0324-721X
Page Range: pp. 217-227
Language: English
Place of Publication: Szeged
Event Title: Conference for PhD Students in Computer Science (1.) (1998) (Szeged)
Related URLs: http://acta.bibl.u-szeged.hu/38508/
Uncontrolled Keywords: Számítástechnika, Kibernetika, Algoritmus
Additional Information: Bibliogr.: 227. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 14. 08:11
URI: http://acta.bibl.u-szeged.hu/id/eprint/12622

Actions (login required)

View Item View Item