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 , 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.
Type de document :
Rapport
[Research Report] RR-6691, INRIA. 2008
Liste complète des métadonnées

Littérature citée [1 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00331248
Contributeur : Ignasi Sau Valls <>
Soumis le : mercredi 15 octobre 2008 - 19:48:13
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : lundi 7 juin 2010 - 20:13:23

Fichiers

RR-6691.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

291

Téléchargements de fichiers

141