Online- und Approximationsalgorithmen

What it is about

You will learn fundamentals and advanced techniques of online and approximation algorithms. In the end you will know classical online problems (e.g., scheduling, paging, k-server), analysis tools such as amortized analysis and randomized algorithms, as well as design techniques for approximation algorithms including LP-relaxation and randomized rounding.

What you will be able to do

• Knowledge of fundamental online problems in resource management, data structures and scheduling
• Understanding and application of amortized analysis
• Familiarity with randomized online algorithms and adversary concept
• Knowledge of central approximation algorithms for Max-Cut, TSP and load balancing
• Design and analysis of polynomial approximation schemes (e.g., knapsack, load balancing)
• Application of LP-relaxation and randomized rounding
• Approximation techniques for Set-Cover and Shortest-Superstring

What the module consists of

• VorlesungDelivery of theoretical content in lectures and through presentations
• ÜbungWork on and discussion of exercise sheets for deepening understanding and individual feedback

Teaching method

• Vortrag/Präsentationfor structured conveying of the lecture content
• Übungsblätter mit Korrekturfor substantive engagement and individual feedback on learning progress
• Übungsbesprechungfor joint solution and clarification of open questions