Max-cut avec bords de poids négatifs

Soit un graphe avec la fonction de poids . Le problème de max-cut consiste à trouver: Si la fonction de pondération n'est pas négative (c'est-à-dire w (e) \ geq 0 pour tous les e \ à E ), il existe alors de nombreuses approximations 2 extrêmement simples pour max-cut. Par exemple, nous pouvons:$G = (V, E, w)$$w:E\rightarrow \mathbb{R}$ arg max S ⊂ V Σ ( u , v ) ∈ E : u ∈ S , v ∉ S w ( u , v ) w ( e ) ≥ 0 e ∈

1. Choisir un sous - ensemble aléatoire de sommets $S$ .
2. Choisissez un ordre sur les sommets et placez chaque sommet $v$ dans $S$ ou $\bar{S}$ pour maximiser les arêtes coupées jusqu'à présent.
3. Améliorations locales: si un sommet de $S$ peut être déplacé vers $\bar{S}$ pour augmenter la coupe (ou inversement), effectuez le déplacement.

L'analyse standard de tous ces algorithmes montre en réalité que la coupe résultante est au moins aussi grande que $\frac{1}{2}\sum_{e \in E}w(e)$ , ce qui est une limite supérieure sur $1/2$ le poids de la coupe maximale si $w$ est non négatif - mais si certaines arêtes ont un poids négatif, ne l’est pas!

Par exemple, l'algorithme 1 (choisir un sous-ensemble aléatoire de sommets) peut clairement échouer sur les graphiques avec des poids d'arêtes négatifs.

Ma question est:

Existe-t-il un algorithme combinatoire simple qui donne une approximation O (1) du problème de max-cut sur les graphes pouvant avoir des poids négatifs?

Pour éviter le problème éventuellement délicat de la valeur de prise max-cut $0$ , je vais autoriser que $\sum_{e \in E}w(e) > 0$ et / ou être satisfait des algorithmes entraînant une petite erreur additive en plus de une approximation de facteur multiplicatif.

Voici ma première tentative d'argumentation. C'était faux, mais je l'ai corrigé après "EDIT:"

Si vous pouviez résoudre efficacement le problème de max-cut avec des poids de bord négatifs, ne pourriez-vous pas l'utiliser pour résoudre le problème de max-cut avec des poids de bord positifs? Commencez avec un problème max-cut que vous souhaitez résoudre et dont la solution optimale est . Maintenant, mettez un grand bord négatif de poids (avec le poids ) entre et . La solution optimale du nouveau problème est , notre algorithme d'approximation hypothétique vous donnera donc une solution avec une coupure maximale dont la valeur est au plus inférieure à optimale. Sur le graphique d'origine, la réduction maximale est toujours au maximum inférieure à optimale. Si vous choisissez proche deb - un u v b - a ( b - a ) / 2 ( b - a ) / 2 a b ≠ seize /$b$$-a$$u$$v$$b-a$$(b-a)/2$$(b-a)/2$$a$$b$, ceci viole le résultat d'inapproximabilité que si P NP, vous ne pouvez pas approximer la réduction maximum avec un facteur supérieur à . $\neq$$16/17$

MODIFIER:

L'algorithme ci-dessus ne fonctionne pas car vous ne pouvez pas garantir que et trouvent de part et d'autre de la coupe dans le nouveau graphique, même s'ils l'étaient à l'origine. Je peux résoudre ce problème comme suit, cependant.u $u$$v$

Supposons que nous ayons un algorithme d'approximation qui nous donnera une réduction dans un facteur 2 de l'OPT tant que la somme de tous les poids des arêtes est positive.

Comme ci-dessus, commencez par un graphique avec toutes les pondérations non négatives sur les arêtes. Nous allons trouver un graphe modifié avec quelques poids négatifs de telle sorte que si nous pouvons approximer la coupe maximale de dans un facteur de 2, nous pouvons très bien approcher la coupe maximale deG G ∗ G $G$$G^*$$G^*$$G$

Choisissez deux sommets et et espérez qu’ils se trouvent de part et d’autre de la coupe maximale. (Vous pouvez répéter cette opération pour tous les possibles afin de vous assurer que vous essayez d'essayer.) Maintenant, placez un poids négatif important sur toutes les arêtes et pour , et a grand poids positif sur le bord . Supposons que la coupe optimale a un poids .u $u$$v$v - d ( u , x ) ( v , x ) x ≠ u , v a ( u , v ) O P $v$$-d$$(u,x)$$(v,x)$$x \neq u,v$$a$$(u,v)$$OPT$

Une coupe de valeur en , où les sommets et sont du même côté de la coupe, a maintenant la valeur en où est le nombre de sommets de l’autre côté de la coupe. Une coupe avec sur les côtés opposés avec la valeur d'origine maintenant la valeur . Ainsi, si nous choisissons assez grand, nous pouvons forcer toutes les coupes avec et du même côté à avoir une valeur négative. Ainsi, s'il y a une coupe avec une valeur positive, la coupe optimale dans aura alors etc G u v c - 2 d m m ( u , v ) c c + a - ( n - 2 ) d d u v G ∗$c$$G$$u$$v$$c - 2dm$$m$$(u,v)$$c$$c + a - (n-2)d$$d$$u$$v$$G^*$$u$v ( a - ( n - 2 ) d ) u $v$sur les côtés opposés. Notez que nous ajoutons un poids fixe à toute coupe avec et sur les côtés opposés.$(a - (n-2)d)$$u$$v$

Soit . Choisissez pour que (nous le justifierons plus tard). Une coupe de poids en ayant et sur les côtés opposés devient maintenant une coupe de poids . Cela signifie que la coupe optimale en a un poids de . Notre nouvel algorithme trouve une réduction de avec un poids d'au moins . Cela se traduit par une coupure dans le graphe original avec un poids d'au moins (puisque toutes les coupes dans avec un poids positif séparéf = ( a - ( n - 2 ) d ) une f ≈ - 0,98 O P T c G u v c - 0,98 O P T G * 0,02 O P T G * 0,01 O P T G 0,99 O P T G * u $f=(a - (n-2)d)$$a$$f \approx - 0.98 OPT$$c$$G$$u$$v$$c - 0.98 OPT$$G^*$$0.02 OPT$$G^*$$0.01 OPT$$G$$0.99OPT$$G^*$$u$ et ), ce qui est meilleur que le résultat d'inapproximabilité.$v$

Il n'y a pas de problème avec le choix assez grand pour faire une coupe avec et sur le même négatif côté, puisque nous pouvons choisir aussi grand que nous voulons. Mais comment avons-nous choisi pour que alors que nous ne connaissions pas ? Nous pouvons approcher vraiment bien ... si nous laissons la somme des poids des arêtes de , on sait . Nous avons donc une plage de valeurs assez étroite pour , et nous pouvons itérer sur prenant toutes les valeurs comprises entre etd u v d a f ≈ - .99 O P T O P T O P T T G $d$$u$$v$$d$$a$$f \approx -.99OPT$$OPT$$OPT$$T$$G$2 T≤OPT≤Tff-.49T-.99T0,005Tf≈-0,98OP$\frac{1}{2}T \leq OPT \leq T$$f$$f$$-.49T$$-.99T$à des intervalles de . Pour l'un de ces intervalles, nous sommes assurés d'obtenir une valeur d' , ce qui garantit que l' une de ces itérations donnera une bonne coupe.$0.005T$$f \approx -0.98 OPT$

Enfin, nous devons vérifier que le nouveau graphique a des poids de bord dont la somme est positive. Nous avons commencé avec un graphe dont les arêtes pondérées avaient la somme et avons ajouté à la somme des arêtes. Depuis , tout va bien T f - .99 T ≤ f ≤ - .49 $T$$f$$-.99T \leq f \leq -.49T$

Dans l'article " Approximate Max Cut " de S. Har-Peled, la dernière ligne du document mentionnait que la version pondérée réelle de max-cut avait été discutée dans

Rapprochement de la norme de coupe via l'inégalité de Grothendieck , Noga Alon et Assaf Naor, SIAM Journal on Computing, 2006.

Il s’agit bien d’un algorithme SDP, et il me semble que le ratio d’approximation est de 0,56, bien que je ne sois pas sûr que la réduction évoquée dans le document préserve le ratio. Peut-être qu’un examen approfondi du document aidera!

Votre problème a une approximation logarithmique par réduction à un problème de programmation quadratique.

Le problème MaxQP est le problème de l’approximation de la forme quadratique x T M x pour une matrice n × n M , où x est supérieur à { ± 1 } n . MaxCut peut être écrit sous cette forme en définissant M = $x^TMx$$n \times n$$M$$x$$\{\pm 1\}^n$2 n (∑we)I-12 AoùIest la matrice d'identité etAest la matrice d'adjacence. L'algorithme MaxQP de Charikar et Wirthdonne uneapproximation deO(logn)pour MaxQP tant queMa une diagonale non négative. Donc, tant que∑we≥0, MaxCut avec des poids négatifs a une approximation logarithmique.$M = \frac{1}{2n}(\sum{w_e})I - \frac{1}{2}A$$I$$A$$O(\log n)$$M$$\sum{w_e} \geq 0$