Approximation Algorithms ‒ Disopt ‐ EPFL

Lecture

Approximation Algorithms

Lecturer

Description

A large fraction of interesting dicrete optimization problems are NP-hard, that means there is no hope in finding exact, optimum solutions efficiently – all known algorithms for this goal have exponential running time. Hence a growing field in theoretical computer science and discrete mathematics deals with approximation algorithms. These algorithms need only polynomial time and obtain solutions whose values are within a provably small ratio from the optimum. We will present fundamental approximation algorithms for example for

Steiner tree
k-Center
TSP
Set Cover
Knapsack
Multi Constraint Knapsack
Bin Packing (including the AFPTAS by Karmarkar & Karp)
Scheduling on unrelated parallel machines
Scheduling on parallel identical machines
Facility Location
Tree embeddings
MaxCut (via semidefinite programming)
Max-2-Sat (via semidefinite programming)

The lectures and the exercises will be given in English. The only prerequisit is a basic knowledge of algorithms. Please note that this is a theory course, hence there will be no kind of implementation/coding. This is a 4-credit doctoral course. The ID is MATH-724.