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