Wednesday 26
Young researcher contest
Luce Brotcorne
› 15:00 - 15:30 (30min)
› Bât. C - TD 41
Programmation linéaire colorée, équilibre de Nash et pivots
Pauline Sarrabezolles  1@  , Frédéric Meunier  1@  
1 : Centre d'Enseignement et de Recherche en Mathématiques et Calcul Scientifique  (CERMICS)  -  Website
École des Ponts ParisTech (ENPC)
6 et 8 avenue Blaise Pascal Cité Descartes - Champs sur Marne 77455 Marne la Vallée Cedex 2 -  France

Considérons k ensembles de points S_1,...,S_k dans Q^d. Le problème de la programmation linéaire colorée, défini par Barany et Onn (Mathematics of Operations Research, 22 (1997), 550--567), consiste à décider s'il existe un sous-ensemble T dans l'union des S_i tel que T instersecte chaque S_i au plus une fois et contient 0 dans son enveloppe convexe. Dans leur article,Barany et Onn prouvent que ce problème est NP-complet quand k=d. La complexité du cas k=d+1 est laissée en question ouverte dans ce même article. Contrairement au cas k=d ce dernier cas ne devient pas trivial quand les points sont en position générique.

Nous résolvons la question en montrant que ce cas est encore NP-complet. Nous montrons également que si P=NP, alors il existe un algorithme polynomial simple calculant un équilibre de Nash dans un jeu bimatriciel à partir de tout algorithme polynomial résolvant la programmation linéaire coloré pour le cas k=d+1, utilisé comme un sous-programme. Enfin nous proposons une adaptation de l'algorithme de Barany et Onn calculant une solution T dans un cas particulier. Cette adaptation peut être interprétée comme une "Phase I" de la méthode du simplexe.


Online user: 1