Campus Event Calendar
Event Entry
What and Who
Popular matchings in the stable marriage setting
Kavitha Telikepalli
Tata Institute of Fundamental Research, Mumbai
Talk
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 22 June 2012
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We show a linear time algorithm for computing a maximum cardinality popular matching in the stable marriage setting. We then show that for every integer k > 1, there is a matching whose unpopularity is at most k-1 and whose size is at least k/(k+1).(size of a maximum cardinality matching). Such a matching can be computed efficiently by extending the Gale-Shapley stable matching algorithm.
Contact
Saurabh Ray
--email hidden
passcode not visible
logged in users only
Saurabh Ray, 06/14/2012 12:30 -- Created document.