Online Optimization (4V+2U, 9.0 LP)
|SWS||Type||Course Form||CP (Effort)||Presence-Time / Self-Study|
|-||K||Lecture with exercise classes (V/U)||9.0 CP||186 h|
|2||U||Exercise class (in small groups)||28 h|
|(4V+2U)||9.0 CP||84 h||186 h|
- 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.
- 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.
Further literature will be announced in the lecture; Exercise material is provided.
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)
Requirements for attendance (formal)
References to Course [MAT-52-14-K-7]
|[MAT-52-14-M-7]||Online Optimization||P: Obligatory||4V+2U, 9.0 LP|