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 : Thursday 21 November 2024

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