Résumé : This talk will be on popular matchings in the one-sided preferences model. Popular matchings need not always exist in this model and there is a simple combinatorial algorithm to decide if one exists. We will see an LP-duality inspired algorithm for the more general problem of deciding if a popular assignment (i.e., a popular maximum-matching) exists or not. This algorithm can be generalized to solve the popular common base problem in the intersection of two matroids where one matroid is the partition matroid, this implies the popular arborescence problem (relevant in liquid democracy) can be solved efficiently.

 [Slides.pdf] [vidéo] [vidéo]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr