19205801
Lecture
WiSe 24/25: Discrete Mathematics II - Algorithmic Comb.
Tibor Szabo
Comments
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)
close
Suggested reading
- 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
32 Class schedule
Regular appointments
Tue, 2024-10-15 14:00 - 16:00
Tue, 2024-10-22 14:00 - 16:00
Tue, 2024-10-29 14:00 - 16:00
Tue, 2024-11-05 14:00 - 16:00
Tue, 2024-11-12 14:00 - 16:00
Tue, 2024-11-19 14:00 - 16:00
Tue, 2024-11-26 14:00 - 16:00
Tue, 2024-12-03 14:00 - 16:00
Tue, 2024-12-10 14:00 - 16:00
Tue, 2024-12-17 14:00 - 16:00
Tue, 2025-01-07 14:00 - 16:00
Tue, 2025-01-14 14:00 - 16:00
Tue, 2025-01-21 14:00 - 16:00
Tue, 2025-01-28 14:00 - 16:00
Tue, 2025-02-04 14:00 - 16:00
Tue, 2025-02-11 14:00 - 16:00
Thu, 2024-10-17 14:00 - 16:00
Thu, 2024-10-24 14:00 - 16:00
Thu, 2024-10-31 14:00 - 16:00
Thu, 2024-11-07 14:00 - 16:00
Thu, 2024-11-14 14:00 - 16:00
Thu, 2024-11-21 14:00 - 16:00
Thu, 2024-11-28 14:00 - 16:00
Thu, 2024-12-05 14:00 - 16:00
Thu, 2024-12-12 14:00 - 16:00
Thu, 2024-12-19 14:00 - 16:00
Thu, 2025-01-09 14:00 - 16:00
Thu, 2025-01-16 14:00 - 16:00
Thu, 2025-01-23 14:00 - 16:00
Thu, 2025-01-30 14:00 - 16:00
Thu, 2025-02-06 14:00 - 16:00
Thu, 2025-02-13 14:00 - 16:00