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.