This is the introductory module in area C (Discrete Mathematics) of the Master's Programme in Mathematics. It is also an introductory module in the area "Algorithmics" of the Master's Programme in Computer Science. This course should be attended by beginning master's students (unless they focus on other areas). Basic knowledge in combinatorial algorithms, in particular graphs, network flows, and linear programming, is required (if you understand the contents of Sections 3.4, 7.1, 8.1, 8.2, 8.3, 9.1, 9.2, 9.4, 10.1, 11.1, and 15.3. of the Korte–Vygen book cited below, you are ready to take this course).
This course covers the following topics: connectivity in graphs, Gomory–Hu trees, nonbipartite matching, Edmonds' weighted matching algorithm, generalized matching problems, T-joins and T-cuts, submodular functions, network design, traveling salesman problem, polyhedral combinatorics. Some additional topics may be covered as well, including very recent results.
This course is in English. Most of it will be based on the following book:
Detailed list of topics: (1) What is combinatorial optimization? Example: König's theorem. (2) Three proofs of König's theorem: using graph theory, LP duality, and the max-flow-min-cut theorem. (3) Theorems of Hall, Frobenius, Petersen-Berge. (4) Factor-critical graphs, Tutte's theorem. (5) Odd ear-decompositions, blossoms, alternating forests. (6) Edmonds' cardinality matching algorithm. Gallai-Edmond structure theorem. (7) The perfect matching polytope. Weighted matching algorithm. (8) Matching polytope, Cunningham-Marsh theorem (TDI). (9) b-matchings (polyhedral descriptions). (10) T-joins. Algorithm for minimum-weight T-joins. (11) Seymour's theorems on packing T-cuts and edge-disjoint paths. (12) T-join polyhedron (Edmonds-Johnson), T-join polytope. (13) spanning tree polytope. (14) Christofides' algorithm, subtour polytope, Wolsey's analysis, Path TSP. (15) Edge-connectivity. Gomory-Hu trees. (16) Equivalence of separation and optimization. Minimum-weight T-cut problem. (17) Padberg-Rao theorem: b-matching polytope separation. (18) Blocking clutters, theorems of Fulkerson and Lehman. (19) Matroids, greedy algorithm, matroid polytope, rank function. (20) Submodular functions, examples, submodular function maximization. (21) Deterministic 2-approximation algorithm for submodular function maximization. (22) Polymatroids, polymatroid greedy. (23) Submodular function minimization. (24) Polymatroid intersection. (25) Survivable network design. (26) Solving the SNDP LP relaxation. (27) Primal-dual algorithm for network design. (28) Approximation guarantee of the primal-dual algorithm.
Class hours: | Tuesdays and Thursdays 2–4 pm (14:15–15:45) |
Room: | Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2) |
Exercise classes: | Matthias Kaul, see here. |
Exams: | Oral. Dates: February 10–11 and March 6. |
Prof. Dr. J. Vygen