Note that this course is cross-listed with the ELTE University and is held on their campus. Its schedule is set by ELTE.

Meeting times: Fridays 10:15-Noon, at ELTE deli tomb, D 3-517.

Instructor: Dr. Tamás KIS

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.

Textbook: V.V. Vazirani, Approximation algorithms, Springer, 2001.