Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 14 mai 2024 à 14h00 en B107 & visioconférence, Kavitha Telikepalli nous parlera de : Popular matchings and optimality

Résumé : In this talk we will consider algorithms for finding optimal popular matchings. While it is easy to find max-size popular matchings, it is NP-hard to find a min-cost popular matching. This motivates us to relax popularity to a weaker notion called "quasi-popularity". Describing the popular and quasi-popular matching polytopes is hard, but there is an easy-to-describe integral polytope sandwiched between these two hard ones (see the illustration). So we can efficiently find a quasi-popular matching of cost at most that of a min-cost popular matching.

 [Slides.pdf] [vidéo]

Dernière modification : Tuesday 07 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr