Summer 2024

Approximation Algorithms

Bachelor/Master Course in Summer 2024
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: Dr. Felix Hommelsheim

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:

• Tue 10-12 MZH 3150 and Thu 14-16 MZH 5500
• The Course starts on Tuesday, April 9, at 10:15. Further information on StudIP.

There is the possibility to further extend the content of the course as well as the credits (+3 CP) 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

Seminar: Combinatorial Optimization and Machine Learning

Sommersemester 2024, 3 or 6 CP
03-IMS-COML

This seminar focusses on recent research at the interplay of combinatorial optimization and machine learning. Both fields provide important methods for solving various real-world problems. On the one hand, we study how machine learning techniques can improve well-established solution methods for NP-hard discrete optimization problems. How can untrusted prediction, e.g., machine-learned, be used to derived provable guarantees for the performance of online algorithms? How can machine learning accelerate existing optimization methods? On the other hand, combinatorial optimization problems are increasingly important in machine learning. We will study particular relevant problems such as clustering, feature selection and submodular function optimization.

Lecturer: Dr. Felix Hommelsheim

Format: 

Students are expected to read and thoroughly understand original research papers, and to deliver an oral presentation and a write up.

Most likely the seminar will be virtual via Zoom.

• Organizational meeting: Tuesday, April 10, at 10:15 pm MZH 3150

We will discuss the organization and allocate the research articles in the first meeting. Please register with StudIP. The seminar is planned as a block seminar, meaning that all talks will be at two days in the end of the semester. We will discuss this in the first zoom meeting.