Coupe maxi au carré euclidien en faible dimension

Soit points dans le plan . Considérons un graphique complet avec les points comme sommets et avec des poids de bord de . Pouvez-vous toujours trouver une réduction de poids d'au moins $x_1, \ldots, x_n$ $\mathbb{R}^2$ $\|x_i - x_j\|^2$ du poids total? Sinon, quelle constante devrait remplacer le $\frac 2 3$ ? $\frac 2 3$

Le pire exemple que je puisse trouver est de 3 points sur un triangle équilatéral, qui atteint le . Notez qu'une division aléatoire produirait $\frac 2 3$ , mais il semble intuitivement évident que dans les petites dimensions, on peut mieux se regrouper qu'au hasard. $\frac 1 2$

Que se passe-t-il pour max-k-cut pour k> 2? Que diriez-vous d'une dimension d> 2? Existe-t-il un cadre pour répondre à ces questions? Je connais les inégalités de Cheeger, mais celles-ci s'appliquent à la coupe la plus clairsemée (et non à la coupe maximale) et ne fonctionnent que pour les graphiques réguliers.

(La question est inspirée par le problème du regroupement des sources de lumière dans l'infographie pour minimiser la variance).

ds.algorithms graph-algorithms application-of-theory max-cut clustering Milos Hasan
la source

Il existe une simple approximation 1-2 / k pour Max k-Cut, et pour k> 2, vous pouvez trouver une bonne grosse coupe, mais pour k = 2, vous pouvez voir www-math.mit.edu/~goemans/PAPERS/maxcut -jacm.pdf et sujets connexes, je pense que si vous trouvez une bonne coupe avec une forte probabilité, vous pouvez dire qu'il y a une coupe avec 2/3 ou non, au moins la gamme de possibilités sera limitée.

Saeed

notez cependant que la fonction de poids ici est la distance euclidienne CARRÉE, qui n'est pas une métrique.

Suresh Venkat

Je suppose que max cut a un ptas, ou peut-être même un algorithme de polytime pour ces cas, mais la question spécifique est très intéressante. Est-il clair quelle est la coupe maximale lorsque les sommets sont également espacés le long d'un cycle, et que l'exemple de cette classe qui minimise la coupe maximale est trois sommets également espacés? Parce qu'il pourrait y avoir un argument qui montre que chaque configuration de points peut être convertie en une configuration `` symétrique '' sans augmenter le rapport de la coupe maximale au poids total, et donc il pourrait être suffisant de comprendre uniquement les configurations hautement symétriques

Luca Trevisan

Aussi, que se passe-t-il dans une dimension? Il est possible de trouver une configuration pour laquelle la coupe maximale est d'environ 2/3 du poids total (un point est -1, un point est +1, 4 points sont très proches de zéro; le poids total est 12 et l'optimum est 8). Les 2/3 sont-ils le plus petit rapport possible entre la coupe maximale et le poids total dans 1 dimension?

Luca Trevisan

@Luca: Oui, 1D n'est pas non plus trivial. Intuitivement, la constante devrait se rapprocher de 1/2 à mesure que la dimension augmente. Pour le cas 2D, nous pouvons supposer que le centre de gravité est à (0,0) et que tous les points s'inscrivent dans le cercle unitaire. Il pourrait y avoir un argument de "répulsion des points" qui pousse les points vers le cercle unitaire sans augmenter le poids coupé, ce qui aiderait, mais je ne pouvais pas le cerner.

Milos Hasan

Réponses:

${d+1 \choose 2}$ $(d+1)^2/4$ $\frac 12 \cdot \frac {d+1}{d}$

Luca Trevisan
la source

D'accord, mais pourquoi la configuration de d + 1 points à une distance de 1 constitue-t-elle le pire des cas? Cela semble plausible, mais est-ce évident? (Et pour d = 1, deux points à une distance de 1 ne sont clairement pas le pire des cas; la configuration à 6 points que vous avez donnée ci-dessus est pire. Se pourrait-il que d = 1 soit le seul cas pathologique, et cela fonctionne pour d> = 2?)

Milos Hasan

@milos, je ne suis pas sûr de comprendre. nous savons que 0,5 est réalisable, et cet exemple montre que vous ne pouvez pas faire mieux. Cela ne brise cependant pas les 2/3 de la conjecture de l'avion.

Suresh Venkat

@Suresh: Ce que je cherchais vraiment, c'est de prouver que vous pouvez faire mieux dans les faibles dimensions, c'est-à-dire que je suis intéressé par la séquence des valeurs réelles des pires constantes pour des basses basses particulières.

Milos Hasan

Je voulais vraiment prouver un écart réel entre 1/2 et 2/3 pour un faible d. Cela aurait des conséquences intéressantes, c'est-à-dire que vous pouvez battre la sommation / intégration de Monte Carlo (en divisant votre problème en sous-problèmes intelligemment plutôt qu'aléatoirement), si votre problème est intrinsèquement de faible dimension (beaucoup le sont).

Milos Hasan

\sqrt{1.1}

$\sqrt {1.1}$

Prenez 3 points A, B, C sur un triangle équilatéral et ajoutez 3 autres points D, E, F au centre. Il est clair que vous voulez deux de A, B, C d'un côté de la coupe, alors disons que la coupe sur ces trois points est (AB; C). Maintenant, chacun des points D, E, F doit aller du côté C de la coupe, donc la coupe optimale est (AB; CDEF), et le rapport est facilement vérifié pour être 2/3.

Maintenant, éloignez légèrement chacun des points D, E, F du centre pour former un petit triangle équilatéral. Peu importe dans quelle direction, tant qu'ils sont symétriques autour du centre. Si vous les déplacez sur une distance suffisamment petite, la coupe optimale doit toujours être (AB; CDEF). Considérez la longueur de cette coupe. Les bords (AC, BC) forment 2/3 de la longueur totale des bords (AB, BC, AC). Par symétrie, la longueur totale des bords (AD, AE, AF, BD, BE, BF) est 2/3 de la longueur des bords (AD, AE, AF, BD, BE, BF, CD, CE, CF ). Mais aucun des bords (DE, EF, DF) n'est dans la coupe. Le rapport de cette coupe est donc strictement inférieur aux 2/3.

$(\sqrt{6}-1)/5 \approx .2899$ $.6408$ $2/3$

Peter Shor
la source

1 - O (k^{- α})

$1 - O(k^{-\alpha})$

k

$k$

α > 1

$\alpha > 1$

Je suppose que la bonne réponse n'est pas trop inférieure à 0,64, mais je ne sais pas comment afficher une limite inférieure.

Peter Shor