Module Handbook

  • Dynamischer Default-Fachbereich geändert auf MAT

Module MAT-52-14-M-7

Online Optimization (M, 9.0 LP)

Module Identification

Module Number Module Name CP (Effort)
MAT-52-14-M-7 Online Optimization 9.0 CP (270 h)

Basedata

CP, Effort 9.0 CP = 270 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.
4V+2U MAT-52-14-K-7
Online Optimization
P 84 h 186 h - - PL1 9.0 irreg.
  • About [MAT-52-14-K-7]: Title: "Online Optimization"; Presence-Time: 84 h; Self-Study: 186 h

Examination achievement PL1

  • Form of examination: oral examination (20-30 Min.)
  • Examination Frequency: irregular (by arrangement)
  • Examination number: 86348 ("Online Optimization")

Evaluation of grades

The grade of the module examination is also the module grade.


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.

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 can evaluate competitiveness results and they are able to use the tools introduced in the lecture to independentky design competitive algorithms for online problems. 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.

References to Module / Module Number [MAT-52-14-M-7]

Course of Study Section Choice/Obligation
[INF-88.79-SG] M.Sc. Computer Science Formal Fundamentals [WP] Compulsory Elective
Module-Pool Name
[MAT-52-MPOOL-7] Specialisation Mathematical Optimisation (M.Sc.)
[MAT-AM-MPOOL-7] Applied Mathematics (Advanced Modules M.Sc.)