Competitive Analysis of Online Algorithms for Scheduling Packets with Uniform Lifespans
| Název práce v češtině: | Kompetitivní analýza online algoritmů pro rozvrhování paketů s uniformní životností |
|---|---|
| Název v anglickém jazyce: | Competitive Analysis of Online Algorithms for Scheduling Packets with Uniform Lifespans |
| Klíčová slova: | online algoritmy|rozvrhování paketů|kompetitivní analýza|online rozvrhování|uniformní instance |
| Klíčová slova anglicky: | online algorithms|packet scheduling|competitive analysis|online scheduling|uniform instances |
| Akademický rok vypsání: | 2023/2024 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | Mgr. Pavel Veselý, Ph.D. |
| Řešitel: | Matúš Mitro - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 31.01.2024 |
| Datum zadání: | 31.01.2024 |
| Datum potvrzení stud. oddělením: | 01.02.2024 |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| 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. |