Corte euclidiano al cuadrado en dimensiones reducidas

Sea $x_1, \ldots, x_n$ puntos en el plano $\mathbb{R}^2$ . Considere una gráfica completa con los puntos como vértices y con pesos de arista de $\|x_i - x_j\|^2$ . ¿Siempre puedes encontrar un corte de peso que sea al menos $\frac 2 3$ del peso total? Si no, qué constante debería reemplazar a $\frac 2 3$ ?

El peor ejemplo que puedo encontrar es 3 puntos en un triángulo equilátero, que logra el $\frac 2 3$ . Tenga en cuenta que una división aleatoria produciría $\frac 1 2$ , pero parece intuitivamente obvio que en dimensiones bajas, uno puede agruparse mejor que al azar.

¿Qué sucede para max-k-cut para k> 2? ¿Qué tal una dimensión d> 2? ¿Existe un marco para responder a esas preguntas? Conozco las desigualdades de Cheeger, pero se aplican al corte más escaso (no al corte máximo) y solo funcionan para gráficos regulares.

(La pregunta se inspira en el problema de agrupar fuentes de luz en gráficos de computadora para minimizar la variación).

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

Hay una aproximación simple de 1-2 / k para Max k-Cut, y para k> 2 puede encontrar un buen corte grande pero para k = 2 puede ver www-math.mit.edu/~goemans/PAPERS/maxcut -jacm.pdf y temas relacionados, creo que si encuentra un buen corte con alta probabilidad, puede decir que hay un corte con 2/3 o no, al menos el rango de posibilidades será limitado.

Saeed

Sin embargo, tenga en cuenta que la función de peso aquí es la distancia euclidiana CUADRADA, que no es una métrica.

Suresh Venkat

Supongo que max cut tiene un ptas, o tal vez incluso un algoritmo polytime para estas instancias, pero la pregunta específica es muy interesante. ¿Está claro cuál es el corte máximo cuando los vértices están igualmente espaciados a lo largo de un ciclo, y que el ejemplo en esta clase que minimiza el corte máximo es tres vértices igualmente espaciados? Debido a que podría haber un argumento que muestra que cada configuración de puntos se puede convertir a una configuración "simétrica" sin aumentar la relación de corte máximo al peso total, por lo que podría ser suficiente para entender solo configuraciones altamente simétricas

Luca Trevisan

Además, ¿qué sucede en una dimensión? Es posible encontrar una configuración para la cual el corte máximo sea aproximadamente 2/3 del peso total (un punto es -1, un punto es +1, 4 puntos están muy cerca de cero; el peso total es 12 y el óptimo es 8). ¿Es 2/3 la relación más pequeña posible de corte máximo al peso total en 1 dimensión?

Luca Trevisan

@Luca: Sí, 1D tampoco es trivial. Intuitivamente, la constante debería acercarse a 1/2 a medida que aumenta la dimensión. Para el caso 2D, podríamos suponer que el centro de gravedad está en (0,0) y que todos los puntos se ajustan dentro del círculo unitario. Puede haber algún argumento de "repulsión de puntos" que empuje los puntos hacia el círculo de la unidad sin aumentar el peso del corte, lo que ayudaría, pero no pude fijarlo.

Milos Hasan

Respuestas:

La constante tiende a 1/2 a medida que aumenta la dimensión. En d dimensiones, puede tener d + 1 puntos a una distancia uno del otro, por lo que la suma de la distancia al cuadrado es y el corte máximo es como máximo , que es una fracción de del peso total ${d+1 \choose 2}$ $(d+1)^2/4$ $\frac 12 \cdot \frac {d+1}{d}$

Luca Trevisan
fuente

Bien, pero ¿por qué la configuración de puntos d + 1 a una distancia de 1 constituye el peor de los casos? Esto parece plausible, pero ¿es obvio? (Y para d = 1, dos puntos a una distancia uno de otro claramente no son el peor de los casos; la configuración de 6 puntos que proporcionó anteriormente es peor. Podría ser que d = 1 es el único caso patológico, y funciona para d> = 2?)

Milos Hasan

@milos No estoy seguro de entender. sabemos que se puede lograr 0.5, y este ejemplo muestra que no puede hacerlo mejor. Sin embargo, no rompe la conjetura de 2/3 para el avión.

Suresh Venkat

@Suresh: Lo que estaba realmente después está demostrando que se puede hacer mejor en bajas dimensiones, es decir, estoy interesado en la secuencia de los valores reales de las peores constantes para particular, bajo d's.

Milos Hasan

Tenía muchas ganas de demostrar una brecha real entre 1/2 y 2/3 para baja d. Esto tendría consecuencias interesantes, es decir, que puede superar la suma / integración de Monte Carlo (dividiendo su problema en subproblemas de forma inteligente en lugar de aleatoriamente), si su problema es intrínsecamente de baja dimensión (muchos lo son).

Milos Hasan

Aunque esto es solo una respuesta para la gran d, muestra qué tipo de dificultades pueden surgir en el análisis del caso de la pequeña d. Suponga que, en 2 dimensiones, podría tener cinco puntos cuya distancia al cuadrado por pares esté entre 1 y 1.1. Entonces el peso total es de al menos 10 y el corte máximo es de 6.6 como máximo. Si 2/3 es la respuesta correcta para dos dimensiones, debe ser capaz de demostrar que si tiene cinco puntos de manera que todas las distancias euclidianas por pares sean al menos una, una de las distancias euclidianas por pares es al menos . ¿Cómo argumenta eso?

\sqrt{1.1}

$\sqrt {1.1}$

Luca Trevisan

Tome 3 puntos A, B, C en un triángulo equilátero y agregue 3 puntos más D, E, F, en el centro. Está claro que quiere dos de A, B, C en un lado del corte, así que digamos que el corte en estos tres puntos es (AB; C). Ahora, cada uno de los puntos D, E, F tiene que ir del lado C del corte, por lo que el corte óptimo es (AB; CDEF), y la relación se verifica fácilmente para que sea 2/3.

Ahora, mueva cada uno de los puntos D, E, F ligeramente lejos del centro para formar un pequeño triángulo equilátero. No importa en qué dirección, siempre que sean simétricos alrededor del centro. Si los mueve una distancia lo suficientemente pequeña, el corte óptimo aún debe ser (AB; CDEF). Considere la longitud de este corte. Los bordes (AC, BC) forman 2/3 de la longitud total de los bordes (AB, BC, AC). Por simetría, la longitud total de los bordes (AD, AE, AF, BD, BE, BF) es 2/3 de la longitud de los bordes (AD, AE, AF, BD, BE, BF, CD, CE, CF ) Pero ninguno de los bordes (DE, EF, DF) está en el corte. Entonces, la proporción de este corte es estrictamente menor que 2/3.

Debería poder optimizar esta construcción para encontrar una configuración donde el corte óptimo sea significativamente menor que 2/3. Al intentarlo, entiendo que si tomas seis puntos dispuestos en dos triángulos equiláteros que tienen el mismo centro, con el más pequeño del tamaño del más grande, entonces el máximo convierte en el peso total en lugar de . $(\sqrt{6}-1)/5 \approx .2899$ $.6408$ $2/3$

Peter Shor
fuente

1 - O (k^{- α})

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

k

$k$

α > 1

$\alpha > 1$

Supongo que la respuesta correcta es algo no muy inferior a .64, pero no tengo idea de cómo mostrar un límite inferior.

Peter Shor