Approximation Algorithms

This course is taught in English. This course was offered in the summer term 2022 (Link to official course page).

Description

In the presence of well-established conjectures on computational hardness such as P != NP  there are many optimization problems that cannot be solved to optimality in an amount of  time acceptable to most practitioners. The field of approximation algorithms aims to provide a workaround by designing algorithms which compute non-optimal solutions in polynomial time, while providing some guarantee that the resulting solution is not too far from optimality.
The seminar will review a range of useful techniques for designing such algorithms, including greedy heuristics, linear relaxations, and discretization. We will also touch on some of the limitations of approximation algorithms, showing that some NP-hard combinatorial problems such as Max-Clique do not even admit good approximation algorithms in polynomial time.

Tasks

The seminar will cover up to 10 topics, depending on the number of participants. Each topic will be covered by one student, who will work through a paper or problem, give a 30 min  presentation on it and write a 1-2 page summary.

Requirements

Basic understanding of algorithms and their analysis. Concepts of polynomial-time, NP-completeness, and problem reductions. Knowledge of LaTeX for typesetting the report.

We are looking for students with an interest in theoretical computer science and algorithm design. Some of the topics to be discussed are fairly technical and experience with graph theory, algorithm analysis, probability theory, and complexity theory will be bene?cial. However, the range of topics is quite wide, so a lack of background in some of these topics should not be an obstacle. The seminar is open to Bachelor and Master students in TM.

Setup

There will be an initial meeting to give an overview over the subject and distribute topics. The
seminar itself will be held as a block seminar, at a date to be agreed upon.