Seminar: Approximation Algorithms
Lecturers
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.
News
- 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).