BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/806
DTSTAMP:20230914T125939Z
SUMMARY:Popular Matchings in the Stable Marriage Problem
DESCRIPTION:Speaker: Kavitha Telikepalli\n\nAbstract: \nThe stable marriag
e problem consists of a bipartite graph $G = (A \\cup B\,E)$ where every v
ertex has a ranking of its neighbours in a strict order of preference. Eve
ry stable matching matches the same subset of vertices. In this talk we co
nsider a relaxation of stability called {\\em popularity} -- this notion w
as introduced by Gardenfors in 1975 and it is based on ``global stabilit
y''. A matching is popular if it never loses a head-to-head election again
st any matching where each vertex casts a vote.\n\nA stable matching is a
min-size popular matching and there is a simple and efficient algorithm to
compute a max-size popular matching in $G$. However it is NP-hard to comp
ute a max-utility popular matching when there is a utility function on the
edge set. A max-utility popular {\\em mixed matching}\, i.e.\, a prob
ability distribution over matchings\, could have a much higher utility tha
n all popular matchings in $G$ and it can be computed in polynomial time.
This mixed matching has a simple structure: it is of the form $\\{(M\, \\f
rac{1}{2})\, (M'\,\\frac{1}{2})\\}$ where $M$ and $M'$ are matchings in G.
This structure is due to the self-duality of the linear program that give
s rise to the polytope of popular fractional matchings in $G$.\n
URL:https://www.tcs.tifr.res.in/web/events/806
DTSTART;TZID=Asia/Kolkata:20170905T160000
DTEND;TZID=Asia/Kolkata:20170905T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR