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.
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.
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.
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.