Campus Event Calendar
Event Entry
What and Who
Popularity, Mixed Matchings, and Self-duality
Kavitha Telikepalli
School of Technology & Computer Science Tata Institute of Fundamental Research, Mumbai
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 11 May 2017
13:00
60 Minutes
Warning: Title has changed!
E1 5 -MPI for Softwaresystems
R 029
Saarbrücken
Warning: New Building!
Warning: New Room!
Abstract
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)
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)
Contact
Moti Medina
--email hidden
passcode not visible
logged in users only
Moti Medina, 05/10/2017 13:47
Moti Medina, 04/26/2017 11:04
Moti Medina, 04/21/2017 10:28
Moti Medina, 02/22/2017 13:37 -- Created document.
Moti Medina, 04/26/2017 11:04
Moti Medina, 04/21/2017 10:28
Moti Medina, 02/22/2017 13:37 -- Created document.