Online Algorithms for Packet Scheduling
| Název práce v češtině: | Online algoritmy pro rozvrhování paketů |
|---|---|
| Název v anglickém jazyce: | Online Algorithms for Packet Scheduling |
| Klíčová slova: | online algoritmy; kompetitivní analýza; online rozvrhování; buffer management; resource augmentation |
| Klíčová slova anglicky: | online algorithm; competitive analysis; online scheduling; buffer management; resource augmentation |
| Akademický rok vypsání: | 2014/2015 |
| Typ práce: | disertační práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | prof. RNDr. Jiří Sgall, DrSc. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 26.09.2014 |
| Datum zadání: | 26.09.2014 |
| Datum potvrzení stud. oddělením: | 05.08.2015 |
| Datum a čas obhajoby: | 25.09.2018 00:00 |
| Datum odevzdání elektronické podoby: | 17.07.2018 |
| Datum odevzdání tištěné podoby: | 17.07.2018 |
| Datum proběhlé obhajoby: | 25.09.2018 |
| Oponenti: | Clifford Stein |
| Matthias Englert | |
| Zásady pro vypracování |
| Cílem práce je navrhnout a analyzovat nové online algoritmy pro rozvrhování paketů. Zaměří se kromě klasických modelů také na tzv. modely s "resource augmentation", kdy online algoritmus má výhodu spočívající např. ve vyšší rychlosti procesoru anebo v částečné informaci o budoucím vstupu. |
| Seznam odborné literatury |
| D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.
A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998. Aktuální konferenční a časopisecké články |