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...
Saved in:
| Main Author: | |
|---|---|
| Corporate Author: | |
| 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 |
| 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 |