Advanced Student Seminar: Approximation Algorithms for Combinatorial Optimization

Lecturers

Prof. Dr. Andreas Schulz, Daniel Vaz

Description

NP-complete optimization problems cannot be solved in polynomial time (unless P=NP). One way to obtain efficient algorithms anyway is to relax optimality. An approximation algorithm is an algorithm that runs in polynomial time and computes a feasible solution with an objective function value that is within a certain factor of that of an optimal solution. This seminar covers recent results as well as advanced techniques in the field. Participants are assigned research papers and are expected to deliver a presentation, demonstrating in-depth understanding of the discussed problem, key technical ideas and proofs, related bibliography, and open questions.

The presentations will take place in English.

Literature

Discrete Optimization (MA3502) or Combinatorial Optimization (MA4502)

The materials and presentations made available to you for educational purposes are copyrighted work. We ask you to observe the applicable copyright law. You may only use these copyrighted materials for the purposes of your studies. Any further use requires the explicit prior consent of the copyright holder. In particular, it is not permitted to record (recording on your own computer of either synchronous or asynchronous teaching units), share them with third parties, reproduce them publicly or use them for commercial purposes.