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, Baranya), (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)
Further information about the course will be available at the course website: http://discretemath.imp.fu-berlin.de/DMII-2018-19/