Combinatorial Optimization, Winter 2022

Instructor: Yasamin Nazari

homepage: https://www.cs.jhu.edu/~ynazari/ email: ynazari [AT] cs.sbg.ac.at

Office hours: Monday 14:30-15:00 (or by email)

Lectures (VO) -Mondays 13:00-14:30, T04:

10/10/2022:
- Max Flow 1: Review of graph theory concepts, cuts and flows, max flow min cut theorem, augmenting paths
- Notes: Class will be in T05 only this week.
- Material: Section 8 of KV book. Lecture notes by Michael Dinitz.
17/10/2022:
- Max Flow 2: Algorithms for max flow- min cut, Ford-Fulkerson and Edmonds-Karp
- Material: Section 8.3 of of KV book. Section 3 of Lecture notes by Michael Dinitz.
24/10/2022
- Graph Matching: Bipartite matching via max flow, matching augmenting paths algorithm. Scribe notes of Cliff Stein for bipartite matching. Optional material: Blossom's algorithm, Lecture Notes by Michel Goemans
31/10/2022
- No class this week (PS and VO): No classes Monday-Wednesday at University
7/11/2022
- Convex sets, Linear Programming, Polytopes. Section 2.1 and 2.2 (partially) of Lecture Notes by Alexander Schriiver, Section 3.1 and 3.4 of KV book.
14/11/2022
- Antonis holds make up practice session (Yasamin away at a workshop)
21/11/2022
- Linear Programming Duality, Lecture notes by Michael Dinitz. See also first part of these notes by Zachary Friggstad
28/11/2022
- Separating hyperplane theorem and separation oracles, NP completeness of Integer Programming and Approximation Algorithms
- Part 1: Section 2.1 and Section 9.1 of Lecture Notes by Alexander Schrijver. Section 9.2 and 9.4 of Lecture notes by Michael Dinitz.
5/12/2022
- Continued discussion on LP rounding for approximation algorithms, Greedy set cover (Lecture notes by Michael Dinitz and Section 1.6 of WS book).
12/12/2022
- Greedy k-Center. Section 2.2 of WS book.
19/12/2022
- Randomized rounding for LPs, Set Cover (lecture notes by Micheal Dinitz and Section 1.7 of WS book) and Min cut (lecture notes and Section 8.1 of WS book).
9/01/2023
- Multiplicative weights update method with application in solving linear programs.
- Reading material: Sections 1 and 2 of survey by Arora, Hazan and Kale.
16/01/2023
- Continued discussion on MWU for LP solving (see Section 2 of the scribe notes of Ola Svensson, and Sections 3.3 and 3.4 of the survey above)
23/01/2023
- No class (VO or PO) this week. Both instructors away at a conference
30/01/2023
- Office hours in regular class time (no lecture, answering questions reviewing course material upon request)
6/02/2023
- Oral final exam. Register for the exam and contact me for scheduling the time. If this time does not work, contact me for another time in the same week.

TA (PS): Antonis Skarlatos - Wednesdays 11:00-11:45, T04

Email: antonisskarlatosj@gmail.com, antonis.skarlatos@plus.ac.at

Assignments to be handed in:

Assignment Set 1 (submission deadline: 14/11/22)
Assignment Set 2 (submission deadline: 19/12/22)
Assignment Set 3 (submission deadline: 27/01/23)

Homework Rules: You can discuss the assignments with your classmates, but you should write-up the solution yourself. Please do not look up solutions, but if you use other notes or online resources, cite the source. Please try to typeset the solutions (but you can add drawn pictures on paper). Assignments can be submitted by paper in class or by email to Antonis.

Exercises for practice (do no need to be handed in): set 1

Resources

Approximation Algorithms by David Williamson and David Shmoys: https://www.designofapproxalgs.com/book.pdf
Lecture notes by Alexander Schrijver: https://homepages.cwi.nl/~lex/files/dict.pdf
Approximation Algorithms lecture notes by Michael Dinitz: https://www.cs.jhu.edu/~mdinitz/classes/ApproxAlgorithms/Spring2021/
Combinatorial Optimization book, Theory and Applications by Benhard Korter and Jens Vygen (available online: https://link.springer.com/book/10.1007/978-3-662-56039-6)
Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver.

Page updated

Google Sites

Report abuse