Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

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

SWS 2V+1U
CP, Effort 4.5 CP = 135 h
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Lecturers
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Additional informations
Livecycle-State [NORM] Active

Notice

This course is a part of the course [MAT-52-14-K-7].

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.

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