Unique Games Conjecture - Relevance

Relevance

Approximation results assuming P ≠ NP versus UGC
Problem Poly-time approx. NP Hardness UGC Hardness
Max 2-Sat 0.940... 0.954...+ε 0.940...+ε
Max Cut 0.878... 0.941...+ε 0.878...+ε
Min Vertex Cover 2 1.360...-ε 2-ε

The unique games conjecture was introduced by Subhash Khot in 2002 in order to make progress on certain questions in the theory of hardness of approximation.

The truth of the unique games conjecture would imply the optimality of many known approximation algorithms (assuming P ≠ NP). For example, the approximation ratio achieved by the algorithm of Goemans and Williamson for approximating the maximum cut in a graph is optimal to within any additive constant assuming the unique games conjecture and P ≠ NP.

A list of results that the unique games conjecture is known to imply is shown in the table to the right together with the corresponding best results for the weaker assumption P≠NP. A constant of c+ε or c-ε means that the result holds for every constant (with respect to the problem size) strictly greater than or less than c, respectively.

Read more about this topic:  Unique Games Conjecture

Famous quotes containing the word relevance:

    “Wherever the relevance of speech is at stake, matters become political by definition, for speech is what makes man a political being.”
    —Hannah Arendt (1906–1975)

    “The most striking fault in work by young or beginning novelists, submitted for criticism, is irrelevance—due either to infatuation or indecision. To direct such an author’s attention to the imperative of relevance is certainly the most useful—and possibly the only—help that can be given.”
    —Elizabeth Bowen (1899–1973)

    “... whatever men do or know or experience can make sense only to the extent that it can be spoken about. There may be truths beyond speech, and they may be of great relevance to man in the singular, that is, to man in so far as he is not a political being, whatever else he may be. Men in the plural, that is, men in so far as they live and move and act in this world, can experience meaningfulness only because they can talk with and make sense to each other and to themselves.”
    —Hannah Arendt (1906–1975)