Csaba Béla: On the partitioning algorithm. In: Acta cybernetica, (14) 2. pp. 217-227. (1999)
Preview |
Cikk, tanulmány, mű
cybernetica_014_numb_002_217-227.pdf Download (1MB) | Preview |
Abstract
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 |
