On the Hardness of General Caching

• Název práce v češtině: O těžkosti obecného cachování
• Název v anglickém jazyce: On the Hardness of General Caching
• Klíčová slova: caching, general caching, NP-hardness, work function
• Klíčová slova anglicky: cachování, obecné cachování, NP-těžkost, work function
• Akademický rok vypsání: 2014/2015
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. RNDr. Jiří Sgall, DrSc.
• Řešitel: Mgr. Lukáš Folwarczný - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 22.02.2015
• Datum zadání: 24.02.2015
• Datum potvrzení stud. oddělením: 26.02.2015
• Datum a čas obhajoby: 07.09.2015 00:00
• Datum odevzdání elektronické podoby: 28.07.2015
• Datum odevzdání tištěné podoby: 31.07.2015
• Datum proběhlé obhajoby: 07.09.2015
• Oponenti: Mgr. Martin Koutecký, Ph.D.

Zásady pro vypracování

Ř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.

Seznam odborné literatury

- 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.