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:Popularity, Mixed Matchings, and Self-duality
Speaker:Kavitha Telikepalli
coming from:School of Technology & Computer Science Tata Institute of Fundamental Research, Mumbai
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 11 May 2017
Duration:60 Minutes
Please note: New Building!
Building:E1 5 -MPI for Softwaresystems
Please note: New Room!
Room:R 029
Abstract: We consider a generalization of stability called "popularity" and the problem is to find a min-cost popular matching in a stable marriage instance G, when there is a cost function on the edge set. While a max-size (or min-size) popular matching can be computed in linear time, there is no polynomial time algorithm currently known to find a min-cost popular matching in G.

However a min-cost popular "mixed matching" in G, i.e. a probability distribution over matchings, can be computed in polynomial time. We show that this mixed matching has a simple structure: it is of the form {(M, 0.5), (M',0.5)} where M and M' are matchings in G. This structure is due to the self-duality of the linear program that gives rise to the polytope of popular fractional matchings in G.

(Joint work with Chien-Chung Huang)

Name(s):Moti Medina
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Moti Medina, 02/22/2017 01:37 PM
Last modified:
Uwe Brahm/MPII/DE, 05/11/2017 07:01 AM
  • Moti Medina, 05/10/2017 01:47 PM
  • Moti Medina, 04/26/2017 11:04 AM
  • Moti Medina, 04/21/2017 10:28 AM
  • Moti Medina, 02/22/2017 01:37 PM -- Created document.