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...
Elmentve itt :
| Szerző: | |
|---|---|
| Testületi szerző: | |
| Dokumentumtípus: | Cikk |
| Megjelent: |
1999
|
| Sorozat: | Acta cybernetica
14 No. 2 |
| Kulcsszavak: | Számítástechnika, Kibernetika, Algoritmus |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12622 |
| LEADER | 01305nab a2200229 i 4500 | ||
|---|---|---|---|
| 001 | acta12622 | ||
| 005 | 20220614081155.0 | ||
| 008 | 161015s1999 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 1 | |a Csaba Béla | |
| 245 | 1 | 3 | |a On the partitioning algorithm |h [elektronikus dokumentum] / |c Csaba Béla |
| 260 | |c 1999 | ||
| 300 | |a 217-227 | ||
| 490 | 0 | |a Acta cybernetica |v 14 No. 2 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika, Algoritmus | ||
| 710 | |a Conference for PhD Students in Computer Science (1.) (1998) (Szeged) | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12622/1/cybernetica_014_numb_002_217-227.pdf |z Dokumentum-elérés |