max planck institut
informatik
informatik
| << Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |
| 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: | Friday, 22 June 2012 |
|---|---|
| Time: | 13:00 |
| Duration: | 30 Minutes |
| Location: | Saarbrücken |
| Building: | E1 4 - MPI-INF |
| Room: | 024 |
| 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 |
|---|---|
| EMail: | saurabh@mpi-inf.mpg.de |
| Video Broadcast: | No | To Location: |
|---|
| Note: | |
|---|---|
| Attachments, File(s): |
| Created by: | Saurabh Ray, 06/14/2012 12:30 PM | Last modified by: | Uwe Brahm/MPII/DE, 06/22/2012 04:01 AM |