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