Journée-séminaire de combinatoire

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

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

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 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr