Online Algorithms for Packet Scheduling
Thesis title in Czech: | Online algoritmy pro rozvrhování paketů |
---|---|
Thesis title in English: | Online Algorithms for Packet Scheduling |
Key words: | online algoritmy; kompetitivní analýza; online rozvrhování; buffer management; resource augmentation |
English key words: | online algorithm; competitive analysis; online scheduling; buffer management; resource augmentation |
Academic year of topic announcement: | 2014/2015 |
Thesis type: | dissertation |
Thesis language: | angličtina |
Department: | Computer Science Institute of Charles University (32-IUUK) |
Supervisor: | prof. RNDr. Jiří Sgall, DrSc. |
Author: | hidden![]() |
Date of registration: | 26.09.2014 |
Date of assignment: | 26.09.2014 |
Confirmed by Study dept. on: | 05.08.2015 |
Date and time of defence: | 25.09.2018 00:00 |
Date of electronic submission: | 17.07.2018 |
Date of submission of printed version: | 17.07.2018 |
Date of proceeded defence: | 25.09.2018 |
Opponents: | Clifford Stein |
Matthias Englert | |
Guidelines |
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. |
References |
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 |