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.