Seminar "Online Algorithms" WS 2026/27
Enrollment: if you want to take this seminar for the module INF-25-Ma-FTK-Sem “Seminar Theoretical Computer Science and Symbolic AI", please register by completing this survey and enrolling in our OPAL course. Otherwise, just enroll in the OPAL course.
Online Algorithms
An online algorithm is an algorithm that processes its input piece by piece, without having knowledge of it a priori (as it is the case with offline algorithms). Examples include the k-server, paging and ski rental problem.
Bibliography
- Amos Fiat and Gerhard J. Woeginger, Online Algorithms The State of the Art (Springer, 1998)
- Allan Borodin and Ran El-Yaniv, Online Computation and Competitive Analysis (Cambridge University Press, 2005)
The topics will be based on selected chapters from these textbooks and research articles (see below).
Seminars take place at APB/3027 (Selected Mondays, slot 09:20-10:50)
The seminar is open to all students interested in algorithms and theoretical computer science. Prerequisites are some algorithmic background (successful completion of "Algorithmen und Datenstrukturen" or similar) and general mathematical maturity. The language of seminars is English.
Each presentation should take 30-40 mins. You may use any of projector or blackboard. The topics have been classified into three levels of difficulty IMHO and I will consider this in marking. Topics will be allocated in FCFS basis, by emailing me at nicolaos.matsakis@tu-dresden.de your preferred topic and at least three possible dates for your presentation (available dates: All Mondays from 9/Nov/2026 to 14/Dec/2026 inclusive and from 4/Jan/2027 to 25/Jan/2027 inclusive). I will try to allocate two talks per day. You are free to use AI but you are expected to answer questions on your talk/topic just as if you had not used AI. In case you want to present another topic on online algorithms that you have in mind, please let me know. Finally, I will be expecting from you a 2-page report on your talk, emailed to me until Monday 25/1. I will be glad to answer questions on your topic, either by email or in person (office: APB 3002).
List of topics: (topics in italics have been reserved)
1. Amortized efficiency of list update and paging rules, by Sleator and Tarjan,
https://dl.acm.org/doi/pdf/10.1145/2786.2793
(rank 1, basic classic paper)
2. Randomized competitive algorithms for the list update problem, by Reingold et al.,
Sections 1-3 only.
https://link.springer.com/article/10.1007/BF01294261
(rank 2, Probability needed)
3. Competitive paging algorithms, by Fiat et al.,
https://arxiv.org/pdf/cs/0205038,
(rank 2, probability needed)
4. Competitive buffer management for shared-memory switches, by Aiello et al.,
(rank 1)
5. On the k-Server Conjecture, by Koutsoupias and Papadimitriou
https://dl.acm.org/doi/pdf/10.1145/210118.210128
(rank 3, classic (non-trivial) paper)
6. An exposition to the k-server problem, (p.150-163 from the Borodin/El-Yaniv book)
(rank 2)
7. New algorithms for an ancient scheduling problem, by Bartal et al.,
https://dl.acm.org/doi/pdf/10.1145/129712.129718
(rank 2, probability needed)
8. Randomized Primal-Dual Analysis of RANKING for Online Bipartite Matching, by Devanur et al.
https://www.nikhildevanur.com/pubs/RPDFinal.pdf
(rank 3, probability needed)
9. Improving Online Algorithms via ML Predictions, by Kumar et al.
(rank 3, probability needed)
10. A Multiple-Choice Secretary Algorithm with Applications to Online Auctions, by Kleinberg
https://dl.acm.org/doi/pdf/10.5555/1070432.1070519
(rank 2, probability needed)
The first seminar took place on Monday, October 19th 2026. The second seminar took place on Monday, October 19th 2026 (presentation: Breaking the Barrier of 2 for the Competitiveness of Longest Queue Drop ). There will be no seminar on Monday, November 2nd. The next seminar will take place on Monday, December 7th.
The (tentative) schedule for the students' presentations is the following:
Monday December 7th, 2026
- Diehl, Emmanuel - Topic 3
Monday January 11th, 2027
- Chanikya, Balumuru - Topic 1
- Taha, Muhammad - Topic 6
Monday January 18th, 2027
- Hamed, Farahat - Topic 9
- Pin-Ju, Huang - Topic 8