Approximation algorithms are polynomial-time algorithms that guarantee to find a feasible solution that is optimal up to a factor of k. For some NP-hard problems, k can be chosen arbitrarily close to 1, for others there is a best possible constant, and for some problems there is no such constant (unless P=NP). We analyze the approximability of various classcial NP-hard combinatorial optimization problems, including the TSP, set covering, knapsack, bin packing, and satisfiability problems.
This course will be in English. Most of the course will be based on the following book:
For the part on the TSP, see my recent survey paper.
Prerequisites: | Combinatorial Optimization |
(in particular basic knowledge in graphs, linear programming, network flows, matching, and NP-completeness; see, e.g., Chapters 1-15 of my textbook above) | |
Class Hours: | Tuesdays and Thursdays 14:15-15:45 |
Room: | Gerhard-Konow-Hörsaal, Lennéstr. 2 |
Exercise Classes: | Thursdays 16:00-17:30, Sophie Spirkl, see here |
Exams: | Oral exams on July 21 and September 23, scheduled individually |
Professor J. Vygen