max planck institut
MPI-INF or MPI-SWS or Local Campus Event Calendar
What and Who
|Title:||Popular matchings in the stable marriage setting|
|coming from:||Tata Institute of Fundamental Research, Mumbai|
We use this to send out email in the morning.
Date, Time and Location
|Date:||Friday, 22 June 2012|
|Building:||E1 4 - MPI-INF|
|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.|
|Video Broadcast:||No||To Location:|
Tags, Category, Keywords and additional notes
|Created by:||Saurabh Ray, 06/14/2012 12:30 PM||Last modified by:||Uwe Brahm/MPII/DE, 06/22/2012 04:01 AM|
- Saurabh Ray, 06/14/2012 12:30 PM -- Created document.