Summer 2022

Approximation Algorithms

Master Course in Summer 2022
03-ME-602.99a (03-IMAT-APX), 6 CP (+ 3 CP possible)

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial-time algorithms and proving rigorous bounds on their worst case performances.

We review many classical results in the field of approximation algorithms, highlighting different techniques commonly used for the design of such algorithms. Among others, we will treat the following topics:

• Greedy algorithms and Local Search
• Rounding Data and Dynamic Programming 
• Deterministic Rounding of Linear Programs (LPs)
• Random Sampling and Randomized Rounding of LPs
• Primal-Dual Methods
• Hardness of Approximation
• Problem Solving under Uncertainty 

Lecturer: Prof. Dr. Nicole Megow

Time & Format:

We will teach the course with 4 hours per week, where roughly every other week one class will be an interactive exercise session. The course takes place in MZH 6200:

• Tue 08-10 and Thu 14-16
• The Course starts on Thursday, April 21, at 14:15. Further information on StudIP.

There is the possibility to further extend the content of the course as well as the credits by participating in a seminar. This participation consists of individually studying a recent research article and presenting the main results to the rest of the class.  

Examination:

The examination will be by individual oral exam. 

Literature: The course is based on parts of the literature below and recent research articles that will be provided later.

• [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
• [V] Approximation Algorithms, Vijay V. Vazirani
• [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiří Matoušek, Springer, 2012

Hands-on Tutorial on Optimization (engl./dt.)

Block course in Summer 2022 (Sep 26–30)
03-BE-699.12, 3 CP

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems. We develop a toolkit to model real-world problems as (discrete) linear programs. We also explore several ways to find integer solutions such as cutting planes, branch & bound, and column generation.

Throughout the course, we learn these skills by modeling and solving, for example, scheduling, packing, matching, routing, and network-design problems. We focus on translating practical examples into mixed-integer linear programs. We learn how to use solvers (such as CPLEX and Gurobi) and tailor the solution process to certain properties of the problem.

Lecturers: Prof. Dr. Nicole Megow, Dr. Felix Hommelsheim

This course consists of two phases:

• One week Mon-Fri (full day) of lectures and practical labs during Sep 26–30, 2022.
• An individual project period: One project has to be modeled, implemented, and solved individually or in a group of at most two students. The topic will be either developed with or provided by the lecturers. The project including the implementation has to be presented before the beginning of the winter semester.

There are no prerequisites except some basic programming skills to participate.

Important: please register for this course by September 1, 2022 via StudIP  and by Email to Felix Hommelsheim (e-mail address on StudIP).