3/2 - Algorithme probabiliste d'approximation pour MAX-3-COLOR

Question

J'ai ici une question de manuel concernant Max-3-Coloring et j'ai besoin d'aide.J'ai recherché tout type d'informations à ce sujet mais je n'ai rien trouvé de substantiel.Voici la question :

Dans Max-3-Color, vous avez un graphique $ g = (V, E) $ et votre objectif est de trouver une coloration des sommets avec seulement 3 couleurs $ C:V rightarrow [3] $ qui maximise la fonction de qualité $ q (c) $ - le nombre de bords dont les sommets des points de terminaison sont colorés avec différentes couleurs:

$\sum_{(i,j)\in E} (1_{c(i) eq c(j)})$

Donne un probabiliste Algorithme d'approximation $3/2$.(ie $ q (c) geq 2/3 cdot opt ​​$ avec probabilité au moins $ 1- frac {1} {e ^ {k}} $ pour tout $ k in mathbb {n} $

OK, jusqu'à présent, le manuel ne parle que d'un seul algorithme probabiliste qui répond aux exigences : MAX-3-SAT.Le manuel donne un algorithme d'approximation probabiliste de 8/7 $ (pour chaque littéral, lancez une pièce équitable et décidez si vous devez la définir sur $True$ ou $False$).

J'ai également trouvé plusieurs autres sources qui prouvent que le 3-COLOR est NP-Complet en le réduisant au problème 3-SAT.Je suis donc assez convaincu que MAX-3-SAT est la voie à suivre.

D'après ce fil : 3 Réduction de la colorabilité à SAT J'ai pensé à faire la même chose :

Pour chaque $x \in V$, créez trois littéraux :$ x_1, x_2, x_3 in {{true, false} } $ où chaque littéral indique si ledit sommet $ x $ est coloré avec la couleur $ i $.

Ensuite, pour chaque bord $ e = (x, y) in e $ Créez la formule 3-CNF suivante $ varphi $:

$ varphi_e = ( urcorner x_1 vee urcorner y_1 vee urcorner y_1) wedge ( urcorner x_2 vee urcorner y_2 vee urcorner y_2) wedge ( urcorner x_3 vee urcorner y_3 vee vee urcorner y_3) wedge (x_1 vee x_2 vee x_3) $

Et la formule finale $\phi$ est :

$\phi = \bigwedge_{e \in E} \varphi_e$

Chaque formule 3-CNF pour une arête garantit que les deux extrémités ne sont pas de la même couleur et que l'une d'entre elles est de couleur 1, 2 ou 3.

Le problème c'est que je ne vois pas en quoi cela pourrait m'aider.Cela me pose un problème MAX-3-SAT puisque j'ai une formule 3-CNF pour chaque arête et une grande formule 3-CNF pour l'ensemble du graphique.Donc techniquement, je pourrais utiliser le même algorithme que celui donné dans le manuel auparavant.

Mais l'utilisation du même algorithme d'approximation probabiliste $8/7$ pour le MAX-3-SAT ne donnerait-elle pas exactement la même approximation ?alors que je souhaite atteindre une approximation de 3/2$-

Merci à tous ceux qui aident!