Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
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
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.
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html