Seminar: Approximation Algorithms


Prof. Dr. Andreas S. Schulz, Felix Happach, Marcus Kaiser

Brief Description

NP-complete optimization problems likely 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 that is guaranteed to be within a certain factor of the optimal solution.
This seminar covers recent results as well as advanced techniques in the field. Participants will be 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.

  • All presentations have to be given in English.
  • All presentations will be scheduled on one day at the end of the semester.
  • More information will be given at the kick-off meeting.


  • All presentations will take place on Thu July, 11th 2019 in Room 6009 (Karlstr. 45, 6th floor).
  • A list of possible topics is available.
  • Kick-off meeting on Mon April, 29th 2019 at 17:00 in Room 6009 (Karlstr. 45, 6th floor).