Decision Sciences & Systems
Technical University of Munich

Kavitha Telikepalli (Tata Institute of Fundamental Research, Mumbai): Popular Matchings

Wednesday, 06 July 2016 16:00
DSS Seminarraum (01.10.033)

Abstract: In an instance G = (A U B, E) of the stable marriage problem, every vertex has a strict preference list ranking its neighbors in an order of preference. A matching M is popular if for every matching M' we have: the number of vertices that prefer M to M' is at least the number that prefer M' to M. The advantage that we gain by relaxing stability to popularity is the improvement in the size of the resulting matching. In fact, every stable matching is a min-size popular matching and we show a simple linear time algorithm to compute a max-size popular matching.

When each edge has a weight associated with it, we do not yet know how to compute a max-weight popular matching in polynomial time. However we know how to compute a max-weight popular mixed matching in polynomial time -- we show that such a mixed matching has the simple form {(1/2, M), (1/2, M')}.


All Dates

  • Wednesday, 06 July 2016 16:00

Powered by iCagenda

Decision Sciences & Systems (DSS), Department of Informatics (I18), Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany
©2002-2018 DSS All Rights Reserved
Impressum, Privacy Policy, Copyright Information and Disclaimer