Speaker: |
Kavitha Telikepalli |

Organiser: |
Piyush Srivastava |

Date: |
Tuesday, 5 Sep 2017, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

A 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 compute 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 probability distribution over matchings, could have a much higher utility than 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, \frac{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 gives rise to the polytope of popular fractional matchings in $G$.