On the Hardness of General Caching
Thesis title in Czech: | O těžkosti obecného cachování |
---|---|
Thesis title in English: | On the Hardness of General Caching |
Key words: | caching, general caching, NP-hardness, work function |
English key words: | cachování, obecné cachování, NP-těžkost, work function |
Academic year of topic announcement: | 2014/2015 |
Thesis type: | Bachelor's thesis |
Thesis language: | angličtina |
Department: | Computer Science Institute of Charles University (32-IUUK) |
Supervisor: | prof. RNDr. Jiří Sgall, DrSc. |
Author: | Mgr. Lukáš Folwarczný - assigned and confirmed by the Study Dept. |
Date of registration: | 22.02.2015 |
Date of assignment: | 24.02.2015 |
Confirmed by Study dept. on: | 26.02.2015 |
Date and time of defence: | 07.09.2015 00:00 |
Date of electronic submission: | 28.07.2015 |
Date of submission of printed version: | 31.07.2015 |
Date of proceeded defence: | 07.09.2015 |
Opponents: | Mgr. Martin Koutecký, Ph.D. |
Guidelines |
Řešitel bude studovat vhodné speciální případy problému cachování souborů a pokusí se klasifikovat je z hlediska výpočetní složitosti. Cílem jsou buď nové výsledky zesilující známé výsledky o NP-úplnosti z článku Chrobak et al. anebo nové polynomiálně řešitelné podproblémy. |
References |
- A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.
- Chrobak, M., Woeginger, G. J., Makino, K., and Xu, H. Caching is hard – even in the fault model. Algorithmica 63, 4 (2012), 781–794. - Achlioptas, D., Chrobak, M., and Noga, J. Competitive analysis of randomized paging algorithms. Theoretical Computer Science 234, 1-2 (2000), 203–218. - Další odborné články dle konzultace s vedoucím práce. |