Syllabus
Techniques covered:
- Basic definitions, approximation and competitive ratio
- Polynomial-time approximation schemes, their relation to strong NP-hardness
- Advanced use of linear programming in approximation algorithms: rounding, primal-dual algorithms
- Use of semidefinite programming in approximation algorithms
- Use of potential functions for online algorithms
- Methods for proving the hardness of approximation: L-reductions, APX-completeness, PCP theorem
Problems and algorithms covered:
- Various models of scheduling and bin packing, greedy algorithms, further approximation and online algorithms
- Combinatorial problems: Steiner trees, maximal cut, coloring
- Online algorithms for paging (caching) and k-server problem
- Online algorithms for navigation in an unknown environment
Annotation
For many optimization problems it is impossible to find an optimal solution fast. In such case, it is important to study approximation algorithms that work faster, but the solution they find is not necessarily an optimal one.
Sometimes, we also have to react to partial input without knowledge of the complete input, by building a solution step by step. Such algorithms are called on-line. The subject of the course is the study of these two classes of algorithms. We assume knowledge on the level of the Bc. course NDMI084 Introduction to approximation and randomized algorithms.