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.



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

Assignments to be handed in:


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