- competitive analysis for deterministic and randomised algorithms,
- adversary concepts, adaptive and non-adaptive adversaries for randomised algorithms,
- amortized costs, potential method for cost analysis,
- competitive algorithms for paging/caching,
- metrical task systems and request-answer games as concepts for general online problems,
- construction of competitive algorithms for selected online problems (e.g. k-server problem, network routing, packing / covering, scheduling),
- Yao’s principle as a means for constructing lower bounds for randomised online algorithms,
- alternative concepts for the analysis of online problems.
Online Optimization (M, 9.0 LP)
|Module Number||Module Name||CP (Effort)|
|MAT-52-14-M-7||Online Optimization||9.0 CP (270 h)|
|CP, Effort||9.0 CP = 270 h|
|Position of the semester||1 Sem. irreg.|
|Level|| Master (Advanced)|
|Area of study||[MAT-OPT] Optimisation|
|Reference course of study||[MAT-88.105-SG] M.Sc. Mathematics|
|Type/SWS||Course Number||Title||Choice in |
|SL||SL is |
required for exa.
|P||84 h||186 h||-||-||PL1||9.0||irreg.|
- About [MAT-52-14-K-7]: Title: "Online Optimization"; Presence-Time: 84 h; Self-Study: 186 h
Examination achievement PL1
- Form of examination: oral examination (20-30 Min.)
- Examination Frequency: irregular (by arrangement)
- Examination number: 86348 ("Online Optimization")
Evaluation of grades
The grade of the module examination is also the module grade.
Competencies / intended learning achievements
By completing the given exercises, they have developed a skilled, precise and independent handling of the terms, propositions and methods taught in the lecture. They have learnt how to apply the methods to new problems, analyze them and develop solution strategies independently or by team work.
- A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis,
- A. Fiat, G. J. Woeginger: Online Algorithms: The State of the Art,
- D. S. Hochbaum: Approximation Algorithms for NP-hard problems.
Requirements for attendance (informal)
- [MAT-10-1-M-2] Fundamentals of Mathematics (M, 28.0 LP)
- [MAT-14-13-M-3] Linear and Network Programming (M, 9.0 LP)
- [MAT-50-11-M-4] Integer Programming: Polyhedral Theory and Algorithms (M, 9.0 LP)