Topics of the course

• Algorithms and complexity (sorting, Dijkstra, TSP, approximation algorithms, matchings vs Hamiltonicity, P vs NP, certificates (Hall, Tutte), Hungarian algorithm, network flows and its applications (Menger, Baranyai), (list)-coloring, stable matching (Gale-Shapley Algorithm) and its application (Galvin))
• Linear Programming (Simplex Algorithm), Duality and its applications in Combinatorics and Algorithms
• Randomized algorithms (randomized matching algorithms, hypergraph-coloring, derandomization, Erdos-Selfridge Criterion, algorithmic Local Lemma)

• L. Lovász, J. Pelikán, K. Vesztergombi, Discrete Mathematics
• J. Matousek - B. Gaertner, Understanding and Using Linear Programming
• D. West, Introduction to Graph Theory

Further reading:

• V. Chvátal, Linear Programming.
• Schrijver, Theory of Linear and Integer Programming
• Schrijver, Combinatorial Optimization