Competitive Analysis of Online Algorithms for Scheduling Packets with Uniform Lifespans
| Thesis title in Czech: | Kompetitivní analýza online algoritmů pro rozvrhování paketů s uniformní životností |
|---|---|
| Thesis title in English: | Competitive Analysis of Online Algorithms for Scheduling Packets with Uniform Lifespans |
| Key words: | online algoritmy|rozvrhování paketů|kompetitivní analýza|online rozvrhování|uniformní instance |
| English key words: | online algorithms|packet scheduling|competitive analysis|online scheduling|uniform instances |
| Academic year of topic announcement: | 2023/2024 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | angličtina |
| Department: | Computer Science Institute of Charles University (32-IUUK) |
| Supervisor: | Mgr. Pavel Veselý, Ph.D. |
| Author: | Matúš Mitro - assigned and confirmed by the Study Dept. |
| Date of registration: | 31.01.2024 |
| Date of assignment: | 31.01.2024 |
| Confirmed by Study dept. on: | 01.02.2024 |
| Date of electronic submission: | 18.07.2024 |
| Date of submission of printed version: | 18.07.2024 |
| Guidelines |
| Student se z literatury naučí základní techniky pro analýzu online algoritmů pro rozvrhování paketů s termíny. Cílem je prozkoumat tzv. uniformní instance, kde všechny pakety mají stejnou životnost, tedy dobu mezi svým příchodem a termínem na odeslání. Jedním z možných směrů je přesně zanalyzovat chování hladového algoritmu v nejhorším případě, jiným jsou důkazy nových dolních odhadů pro deterministické algoritmy. |
| References |
| Chrobak, M., Jawor, W., Sgall, J. and Tichý, T., 2007. Improved online algorithms for buffer management in QoS switches. ACM Transactions on Algorithms (TALG), 3(4), pp.50:1-50:19.
Chin, F.Y., Chrobak, M., Fung, S.P., Jawor, W., Sgall, J. and Tichý, T., 2006. Online competitive algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms, 4(2), pp.255-276. Andelman, N., Mansour, Y. and Zhu, A., 2003, January. Competitive queueing policies for QoS switches. In SODA (Vol. 3, pp. 761-770). Al-Bawani, K., Englert, M. and Westermann, M., 2018. Comparison-based buffer management in QoS switches. Algorithmica, 80, pp.1073-1092. Goldwasser, M.H., 2010. A survey of buffer management policies for packet switches. ACM SIGACT News, 41(1), pp.100-128. |