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.
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.
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)
- Jan 8th: Introduction, stable matchings problem, Gale-Shapley
algorithm (Ref: Sec 1.1, 1.2 [GI])
- 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])
- Jan 17th: Lattice structure of stable matchings, extensions: sets of unequal size, incomplete lists (Sec 1.3, 1.4 of [GI])
- 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)
- Jan 24th: Counting stable matchings, stable roommates problem
- Jan 29th: Stable roommates continued (Reference)
- Feb 7th: Cheating strategies in the stable marriage problem (Sec 1.7.1, 1.7.2 of [GI])
- Feb 12th: One-sided preferences: Popular matchings with strict lists
- Feb 14th: Popular matchings with ties, a detour to matching theory: Berge's theorem, Gallai-Edmonds decomposition
- Feb 14th: Popular matchings with ties continued (Ref)
- Feb 19th: Hopcroft-Karp algorithm for maximum matching in bipartite graphs (Ref: this and this)
- March 4th: Midsem discussion, algorithm for popular matchings in the stable marriage setting (Ref)
- March 6th: Introduction to rank-maximal matchings and fair
matchings, reduction to min-weight perfect matchings,
integrality of bipartite perfect matching polytope (Ref)
- 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)
- 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)
- March 13th: Edmond's blossom shrinking algorithm (Ref)
Following lectures are available as recorded videos due to the COVID-19 outbreak:
- 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)
- Edmonds-Karp algorithm for max-flow (Ref: CLRS, these notes)
- Flows with lower bounds on edges (Ref: Section 6.7 of Ahuja, Magnanti, Orlin's book, Section 7.7 of Kleinberg-Tardos book)
- Minimum cost circulations: Klein's cycle canceling algorithm, Goldberg-Tarjan algorithm (Ref: these notes)
- Online bipartite matching: Introduction to online algorithms, competitive
ratio, RANKING algorithm of Karp, Vazirani, Vazirani
- Online bipartite matching continued... analysis of RANKING using primal-dual(Ref: the paper and these notes)