Course MAT-52-14A-K-7
Introduction to Online Optimization (2V+1U, 4.5 LP)
Course Type
SWS | Type | Course Form | CP (Effort) | Presence-Time / Self-Study | |
---|---|---|---|---|---|
- | K | Lecture with exercise classes (V/U) | 4.5 CP | 93 h | |
2 | V | Lecture | 28 h | ||
1 | U | Exercise class (in small groups) | 14 h | ||
(2V+1U) | 4.5 CP | 42 h | 93 h |
Basedata
Contents
- competitive analysis for deterministic and randomised algorithms,
- adversary concepts, adaptive and non-adaptive adversaries for randomised algorithms,
- amortised costs, potential method for costs analysis,
- competitive algorithms for paging / caching,
- online scheduling.
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.
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-14A-K-7]
Module | Name | Context | |
---|---|---|---|
[MAT-52-14A-M-7] | Introduction to Online Optimization | P: Obligatory | 2V+1U, 4.5 LP |
Notice