Max-Planck-Institut für Informatik
max planck institut
informatik
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
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Friday, 22 June 2012
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4 - MPI-INF
Room:024
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
Name(s):Saurabh Ray
EMail:saurabh@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
Created by:Saurabh Ray, 06/14/2012 12:30 PMLast modified by:Uwe Brahm/MPII/DE, 06/22/2012 04:01 AM
  • Saurabh Ray, 06/14/2012 12:30 PM -- Created document.