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.