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 |
Datum odevzdání elektronické podoby: | 18.07.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. |