Topics in Algorithms



TA: Ankita Sarkar

The goal of the course is to introduce various aspects of matchings and network flows, including the current research directions in this topic. We will cover broadly the following topics: Matching theory, matchings under preferences including their game theoretic aspects, different variants of network flows (algorithms and applications), and algorithms for matchings in online and dynamic settings. Most of the students have seen matchings and flows to some extent. Matchings under preferences involves finding a matching in a graph that has a set of vertices and edges, and each vertex has a preference ordering on its neighbors. The matching needs to respect the preferences of the vertices, and hence different optimality criteria can be considered to choose a "good" matching. This also raises the question of whether one or more people have an incentive in submitting false preferences.
Roth and Shapley have done seminal work in matchings under preferences, which was awarded the Nobel prize in Economics in 2012.

  • References
    • For stable matchings, we will refer to the book "Stable marriage: Structure and Algorithms" by Gusfield and Irving [GI]. I will post references separately for other topics.
  • Evaluation
    • There will be two quizzes, a midsem, and an endsem. There may be presentations depending on the number of students crediting the course. There will be two assignments/practice problems.
  • Assignments and exam papers

    • Assignment 1 (due on Feb 12th in class)
    Assignment 2 (due on April 27th)
  • Lectures
    1. Jan 8th: Introduction, stable matchings problem, Gale-Shapley algorithm (Ref: Sec 1.1, 1.2 [GI])
    2. Jan 10th: The stable marriage problem with strict and complete lists: correctness, man-optimality, woman-pessimality, weak-pareto optimality (Ref: Sec 1.1, 1.2 [GI])
    3. Jan 17th: Lattice structure of stable matchings, extensions: sets of unequal size, incomplete lists (Sec 1.3, 1.4 of [GI])
    4. Jan 22nd: Stable matchings with indifference (ties): definitions of weakly stable, strongly stable, super-stable matchings, finding weakly stable matchings by breaking ties arbitrarily, 2-approximation to max-cardinality weakly stable matchings (using maximality of stable matchings), 3/2 approximation for ties on one side, example showing that there is no man-optimal weakly stable matching (Reference, and this for the example)
    5. Jan 24th: Counting stable matchings, stable roommates problem
    6. Jan 29th: Stable roommates continued (Reference)
    7. Feb 7th: Cheating strategies in the stable marriage problem (Sec 1.7.1, 1.7.2 of [GI])
    8. Feb 12th: One-sided preferences: Popular matchings with strict lists
    9. Feb 14th: Popular matchings with ties, a detour to matching theory: Berge's theorem, Gallai-Edmonds decomposition
    10. Feb 14th: Popular matchings with ties continued (Ref)
    11. Feb 19th: Hopcroft-Karp algorithm for maximum matching in bipartite graphs (Ref: this and this)
    12. March 4th: Midsem discussion, algorithm for popular matchings in the stable marriage setting (Ref)
    13. March 6th: Introduction to rank-maximal matchings and fair matchings, reduction to min-weight perfect matchings, integrality of bipartite perfect matching polytope (Ref)
    14. March 9th: Half-integrality for general graphs, LP for perfect matchings in general graphs (with odd set constraints), integrality of the polytope (Ref and this)
    15. March 11th: (Guest lecture by Archit) Counting perfect matchings in planar graphs (Ref: Sections 8.2 and 8.3 of Matching theory by Lovász, Plummer)
    16. March 13th: Edmond's blossom shrinking algorithm (Ref)

      17. Following lectures are available as recorded videos due to the COVID-19 outbreak:
    17. Generalizations of matchings: many-to-one, many-to-many, matchings with classifications, reduction to network flows. Recall: network flows definition and notation, max-flow min-cut theorem, Ford-Fulkerson algorithm (Ref: CLRS)
    18. Edmonds-Karp algorithm for max-flow (Ref: CLRS, these notes)
    19. Flows with lower bounds on edges (Ref: Section 6.7 of Ahuja, Magnanti, Orlin's book, Section 7.7 of Kleinberg-Tardos book)
    20. Minimum cost circulations: Klein's cycle canceling algorithm, Goldberg-Tarjan algorithm (Ref: these notes)
    21. Online bipartite matching: Introduction to online algorithms, competitive ratio, RANKING algorithm of Karp, Vazirani, Vazirani
    22. Online bipartite matching continued... analysis of RANKING using primal-dual(Ref: the paper and these notes)