discipline

 Mathematics, Applied mathematics

subject

 Approximation algorithms

lecturers

 Tibor Jordán

credits

 

period

 2 or 4

curriculum

 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 tree

literature

 V. Vazirani, Approximation algorithms, Springer 2003.

form of tuition

Lectures

mode of assessment

written/oral exam