- 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.
Module MAT-52-14A-M-7
Introduction to Online Optimization (M, 4.5 LP)
Module Identification
| Module Number | Module Name | CP (Effort) |
|---|---|---|
| MAT-52-14A-M-7 | Introduction to Online Optimization | 4.5 CP (135 h) |
Basedata
| CP, Effort | 4.5 CP = 135 h |
|---|---|
| Position of the semester | 1 Sem. irreg. |
| Level | [7] Master (Advanced) |
| Language | [EN] English |
| Module Manager | |
| Lecturers | |
| Area of study | [MAT-OPT] Optimisation |
| Reference course of study | [MAT-88.105-SG] M.Sc. Mathematics |
| Livecycle-State | [NORM] Active |
Courses
| Type/SWS | Course Number | Title | Choice in Module-Part | Presence-Time / Self-Study | SL | SL is required for exa. | PL | CP | Sem. | |
|---|---|---|---|---|---|---|---|---|---|---|
| 2V+1U | MAT-52-14A-K-7 | Introduction to Online Optimization
| P | 42 h | 93 h | - | - | PL1 | 4.5 | irreg. |
- About [MAT-52-14A-K-7]: Title: "Introduction to Online Optimization"; Presence-Time: 42 h; Self-Study: 93 h
Examination achievement PL1
- Form of examination: oral examination (20-30 Min.)
- Examination Frequency: irregular (by arrangement)
- Examination number: 86347 ("Introduction to Online Optimization")
Evaluation of grades
The grade of the module examination is also the module grade.
Contents
Competencies / intended learning achievements
Upon successful completion of this module, the students know and understand the issues of online problems as well as the concept of competitive analysis. They have learned to analyse online problems for the existence of competitive algorithms and how to establish lower bounds for deterministic and randomised algorithms. They can derive and prove worst-case performance bounds for online algorithms. They understand the proofs presented in the lecture and are able to reproduce and explain them.
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.
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 Module / Module Number [MAT-52-14A-M-7]
| Module-Pool | Name | |
|---|---|---|
| [MAT-52-MPOOL-7] | Specialisation Mathematical Optimisation (M.Sc.) | |
| [MAT-AM-MPOOL-7] | Applied Mathematics (Advanced Modules M.Sc.) |