IEOR seminar
Speaker: Dr T. Kavitha, TIFR, Mumbai
Title: Popular Matchings and Self-Duality
Date and time: Wednesday, 25 October, 2017, 2 p.m.
Venue: Seminar Room, 2nd Floor, IEOR building
Abstract: The stable marriage problem is a classical and well-studied problem: here the input consists of a bipartite graph G where every vertex has a ranking of its neighbours in a strict order of preference and the goal is to find a "stable matching" in G. Gale and Shapley in 1962 showed
that stable matchings always exist and can be computed efficiently. In this talk we consider a relaxation of stability called popularity -- this notion was introduced in 1975 and it is based on global stability. A matching is popular if it never loses a head-to-head election against any matching
where each vertex casts a vote.
A stable matching is a min-size popular matching and there is a simple and efficient algorithm to compute a max-size popular matching in G. However it is NP-hard to compute a max-utility popular matching when there is a utility function on the edge set. A max-utility popular "mixed matching",
i.e., a probability distribution over matchings, could have a much higher utility than any popular matching in G and it can be computed in polynomial time. This mixed matching has a simple structure: it is of the form {(M, 0.5), (M', 0.5)} where M and M' are matchings in G. This simple structure is due to the self-duality of the linear program that gives rise to the polytope of popular fractional matchings in G.
Speaker profile: Kavitha Telikepalli finished her PhD in 2002 from TIFR. After her post-doc at Max-Planck Institute for Computer Science, Germany, she joined Indian Institute of Science, Bangalore (2005-2010). She has been in TIFR from 2010 onwards. Her main research interests are in
efficient graph algorithms and combinatorial optimization.