|
|
 |
|
Mardi 14 Mai
| Heure: |
14:00 - 15:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Mini course on popular matchings, lecture 2 |
| Description: |
Prof. Kavitha Telikepalli Lecture 2: Popular matchings and optimality.
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. So we can efficiently find a quasi-popular matching of cost at most that of a min-cost popular matching.
This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/. |
|
|
