Conjecture des jeux uniques | EPFL Graph Search

La conjecture des jeux uniques (en anglais Unique Games Conjecture et souvent abrégée UGC) est une conjecture en théorie de la complexité, proposée par Subhash Khot en 2002. Selon cette conjecture, résoudre de manière approximative un certain problème spécifique est NP-difficile. Elle a d'importantes applications relatives à la complexité des algorithmes d'approximation ; le travail qui a été fourni autour de cette conjecture a également permis de démontrer des résultats relatifs à d'autres sujets, par exemple sur la stabilité des systèmes de vote. Subhash Khot a reçu le prix Nevanlinna en 2014 pour son travail sur cette conjecture. Considérons des systèmes d'équations de la forme suivante : où est un entier fixé et connu. La conjecture affirme que, pour tous , si est assez grand, il est NP-difficile, étant donné un tel système d'équations, de dire s'il satisfait l'une ou l'autre des deux propriétés suivantes : Il existe un vecteur qui satisfait une proportion au moins des équations. Aucun vecteur ne satisfait une proportion supérieure à des équations. Il existe plusieurs autres formulations équivalentes de la conjecture, faisant intervenir par exemple l'expansion d'un graphe. La conjecture des jeux uniques permet de démontrer d'autres résultats selon lesquels il est NP-difficile de trouver des solutions approximatives à certains problèmes. En particulier, si elle est vraie, elle implique qu'il est NP-difficile de résoudre approximativement le problème MAX-CUT avec un ratio d'approximation supérieur à environ (ce qui est le ratio atteint par l'algorithme de Goemans et Williamson). Elle implique également qu'obtenir un ratio d'approximation strictement inférieur à , pour le problème de couverture par sommets, est NP-difficile. Sans la conjecture, on peut prouver qu'il est NP-difficile d'obtenir un ratio inférieur à environ . La conjecture des jeux uniques a été définie dans un article de Subhash Khot en 2002.

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349] proved that the problem is NP-hard to approximate within a factor 2- epsilon, assuming the unique games conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the problem is due to Dinur and Safra [Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann. Math. 162(1):439-485]: vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates the vertex cover within a factor 2 - epsilon has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as semidefinite programming relaxations) that approximate the independent set problem within any constant factor have a super-polynomial size.

INFORMS2019

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable candidates for outperforming the current state-of-the-art approximation guarantees for NP-hard problems, for which there still exists a gap between the inapproximability results and the approximation guarantees that we know how to achieve in polynomial time. In this thesis, we address both the power and the limitations of these relaxations, as well as the connection between the shortcomings of these relaxations and the inapproximability of the underlying problem. In the first part, we study the limitations of LP relaxations of well-known graph problems such as the Vertex Cover problem and the Independent Set problem. We prove that any small LP relaxation for the aforementioned problems, cannot have an integrality gap strictly better than

2

and

\omega(1)

, respectively. Furthermore, our lower bound for the Independent Set problem also holds for any SDP relaxation. Prior to our work, it was only known that such LP relaxations cannot have an integrality gap better than

1.5

for the Vertex Cover Problem, and better than

2

for the Independent Set problem. In the second part, we study the so-called knapsack cover inequalities that are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield LP relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. We address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. In the last part, we show a close connection between structural hardness for k-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. This connection is inspired by a family of integrality gap instances of a certain LP relaxation. Assuming the hardness of an optimization problem on k-partite graphs, we obtain a hardness of

2-\varepsilon

for the problem of minimizing the makespan for scheduling with preemption on identical parallel machines, and a super constant inapproximability for the problem of scheduling on related parallel machines. Prior to this result, it was only known that the first problem does not admit a PTAS, and the second problem is NP-hard to approximate within a factor strictly better than 2, assuming the Unique Games Conjecture.

EPFL2017

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best in approximability result for the problem is due to Dinur and Safra: vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP)relaxations of the problem: every LP relaxation that approximates vertex cover within a factor of 2-∈ has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomially many inequalities. © 2015 IEEE.

IEEE Computer Society2015

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

2

and

\omega(1)

1.5

for the Vertex Cover Problem, and better than

2

2-\varepsilon

EPFL2017