Octobre 2023

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Identification des préférences structurées en choix social : quelques résultats algorithmiques et expérimentaux
Description:	Olivier Spanjaard Dans cet exposé, nous présenterons quelques résultats sur la reconnaissance de structures dans les préférences en décision collective. Plus précisément, étant donnée une collection de préférences de votants exprimées sous la forme de relations d'ordre complètes sur un même ensemble de candidats, on cherchera à déterminer si ses préférences respectent une structure commune sur les candidats, et si oui à identifier cette structure. Nous nous intéresserons au cas des préférences unimodales (single-peaked) sur un axe ou sur un graphe quelconque. Nous aborderons à la fois des aspects portant sur la justification de la pertinence des structures identifiées, des aspects algorithmiques et des aspects plus expérimentaux.

Heure:	10:30 - 11:30
Lieu:	Salle A303, bâtiment A, Université de Villetaneuse
Résumé:	Binary non-negative polynomials and convex certificates
Description:	Liding Xu We consider the problem of certifying the non-negativity of polynomials over the Boolean hypercube. We propose a new type of binary non-negativity certificate, which involves the signed support vector of the monomials occurring in the given polynomial. We employ known tools such as max flow and extensions of supermodular functions in order to construct our certificates. Especially, we examine the projected and extended LP formulations for the cone of our binary non-negativity certificates. Based on these tools, we show that a certain family of binary polynomials can be optimized in a fixed-parameter tractable way.