Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

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

SWS 4V+2U
CP, Effort 9.0 CP = 270 h
Position of the semester 1 Sem. irreg.
Level [7] Master (Advanced)
Language [EN] English
Lecturers
Krumke, Sven Oliver, Prof. Dr. (PROF | DEPT: MAT)
+ further Lecturers of the department Mathematics
Area of study [MAT-OPT] Optimisation
Additional informations
Livecycle-State [NORM] Active

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:

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