Sur la Conjecture des Jeux Uniques

Stéphane Pérennes 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : La plupart des problèmes d'optimisation combinatoire sont NP-difficiles, c'est-à-dire qu'ils ne peuvent être résolus en temps polynomial que si les classes P et NP sont identiques. Pour ces problèmes on peut espérer soit trouver des algorithmes d'approximation, soit prouver qu'ils ne peuvent pas être approximés de manière efficace. En 2002 S. Khot formula la Conjecture des Jeux Uniques (UGC), qui géneralise le théorème PCP et impliquerait d'importants résultats d'innaproximabilité pour plusieurs problèmes d'optimisation combinatoire (par exemple Max Cut ou Vertex Cover). Intuitivement, la UGC dit que, pour une certaine classe de jeux, appelés uniques, il est NP-dur de décider si l'on peut trouver une solution proche de l'optimale, ou si toutes les solutions sont loin de l'optimale. Cette conjecture est devenue un problème ouvert des plus importants dans la théorie de la complexité et de l'approximation. Dans cet article nous étudions un problème très relié à la UGC: Max-E$2$-Lin2 dans les graphes bipartis. Dans Max-E$2$-Lin2 on a un graphe $G$ ayant deux type d'arêtes, requérant soit la même soit différente couleur pour ses extrémités. Le but est de 2-colorer les sommets de $G$ en maximisant le nombre d'arêtes satisfaites. Nous prouvons que ce problème est APX-complet dans les graphes bipartis et, en utilisant le Théorème de Répétition Paralèlle, nous discutons les conséquences de ce résultat dans le cadre des jeux uniques et la UGC.
Document type :
Reports
Complete list of metadatas

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00331248
Contributor : Ignasi Sau Valls <>
Submitted on : Wednesday, October 15, 2008 - 7:48:13 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Monday, June 7, 2010 - 8:13:23 PM

Files

RR-6691.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00331248, version 1

Collections

Citation

Stéphane Pérennes. Sur la Conjecture des Jeux Uniques. [Research Report] RR-6691, INRIA. 2008. ⟨inria-00331248⟩

Share

Metrics

Record views

323

Files downloads

158