Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Popular matchings in the stable marriage setting
Speaker:Kavitha Telikepalli
coming from:Tata Institute of Fundamental Research, Mumbai
Speakers Bio:
Event Type:Talk
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Friday, 22 June 2012
Duration:30 Minutes
Building:E1 4
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.
Name(s):Saurabh Ray
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
Created:Saurabh Ray, 06/14/2012 12:30 PM Last modified:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Saurabh Ray, 06/14/2012 12:30 PM -- Created document.