SUBJECT
Title
Approximation algorithms
Type of instruction
lecture
Level
master
Faculty
Part of degree program
Credits
3
Recommended in
Semesters 1-4
Typically offered in
Autumn/Spring semester
Course description
- approximation algorithms for NP-hard problems, basic techniques,
- LP-relaxations. Set cover, primal-dual algorithms. Vertex cover, TSP, Steiner tree, feedback vertex set, bin packing, facility location, scheduling problems, k-center, k-cut, multicut, multiway cut, multicommodity flows, minimum size k-connected subgraphs, minimum superstring, minimum max-degree spanning trees.
Readings
- V.V. Vazirani, Approximation algorithms, Springer, 2001.