Corte maximo euclidiano ao quadrado em dimensões reduzidas

$x_1, \ldots, x_n$ $\mathbb{R}^2$ $\|x_i - x_j\|^2$ $\frac 2 3$ $\frac 2 3$

O pior exemplo que consigo encontrar é 3 pontos em um triângulo equilátero, que atinge o $\frac 2 3$ . Observe que uma divisão aleatória produziria $\frac 1 2$ , mas parece intuitivamente óbvio que em dimensões baixas, é possível agrupar-se melhor do que aleatoriamente.

O que acontece com o max-k-cut para k> 2? Que tal uma dimensão d> 2? Existe uma estrutura para responder a essas perguntas? Conheço as desigualdades de Cheeger, mas elas se aplicam ao corte mais esparso (não ao corte máximo) e funcionam apenas para gráficos regulares.

(A questão é inspirada no problema de agrupar fontes de luz em gráficos de computador para minimizar a variação).

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

Existe uma aproximação simples de 1-2 / k para Max k-Cut, e para k> 2 você pode encontrar um bom corte grande, mas para k = 2 você pode ver www-math.mit.edu/~goemans/PAPERS/maxcut -jacm.pdf e tópicos relacionados, acho que se você encontrar um bom corte com alta probabilidade, poderá dizer que há um corte com 2/3 ou não, pelo menos o intervalo de possibilidades será limitado.

Saeed

observe, no entanto, que a função de peso aqui é a distância euclidiana QUADRADA, o que não é uma métrica.

Suresh Venkat

Eu acho que o corte máximo tem um ptas, ou talvez até um algoritmo polytime para essas instâncias, mas a pergunta específica é muito interessante. Está claro qual é o corte máximo quando os vértices estão igualmente espaçados ao longo de um ciclo, e que o exemplo nesta classe que minimiza o corte máximo são três vértices igualmente espaçados? Como pode haver um argumento que mostra que toda configuração de pontos pode ser convertida em uma configuração `simétrica 'sem aumentar a proporção de corte máximo em relação ao peso total e, portanto, pode ser suficiente entender apenas configurações altamente simétricas

Luca Trevisan

Além disso, o que acontece em uma dimensão? É possível encontrar uma configuração para a qual o corte máximo seja aproximadamente 2/3 do peso total (um ponto é -1, um ponto é +1, 4 pontos estão muito próximos de zero; o peso total é 12 e o ideal é 8). 2/3 é a menor relação possível entre o corte máximo e o peso total em uma dimensão?

Luca Trevisan

@Luca: Sim, 1D também não é trivial. Intuitivamente, a constante deve estar se aproximando de 1/2 à medida que a dimensão aumenta. Para o caso 2D, podemos assumir que o centro de gravidade está em (0,0) e que todos os pontos se encaixam no círculo unitário. Pode haver algum argumento de "repulsão de pontos" que empurra os pontos em direção ao círculo unitário sem aumentar o peso de corte, o que ajudaria, mas não consegui identificá-lo.

Milos Hasan

Respostas:

A constante tende a 1/2 conforme a dimensão aumenta. Nas dimensões d, você pode ter d + 1 pontos à distância um do outro, de modo que a soma da distância ao quadrado é e o corte máximo é no máximo , que é uma fração do peso total ${d+1 \choose 2}$ $(d+1)^2/4$ $\frac 12 \cdot \frac {d+1}{d}$

Luca Trevisan
fonte

OK, mas por que a configuração de d + 1 pontos à distância 1 um do outro constitui o pior caso? Isso parece plausível, mas é óbvio? (E para d = 1, dois pontos a uma distância um do outro claramente não são o pior caso; a configuração de 6 pontos que você deu acima é pior. Será que d = 1 é o único caso patológico e funciona Para d> = 2?)

Milos Hasan

@milos Não sei se entendi. sabemos que 0,5 é possível e este exemplo mostra que você não pode fazer melhor. No entanto, não quebra a conjectura 2/3 do avião.

precisa

@ Suresh: O que eu realmente estava procurando é provar que você pode fazer melhor em baixas dimensões, ou seja, eu estou interessado na sequência de valores reais das piores constantes para determinados baixos d's.

Milos Hasan

Eu realmente queria provar uma diferença real entre 1/2 e 2/3 para d baixo. Isso teria conseqüências interessantes, ou seja, que você pode superar a soma / integração de Monte Carlo (dividindo seu problema em subproblemas de maneira inteligente em vez de aleatória), se o seu problema for intrinsecamente de baixa dimensão (muitos são).

Milos Hasan

Embora seja apenas uma resposta para o d grande, mostra que tipo de dificuldades podem surgir na análise do caso do d pequeno. Suponha que, em 2 dimensões, você possa ter cinco pontos cuja distância ao quadrado ao par esteja entre 1 e 1,1. Então o peso total é de pelo menos 10 e o corte máximo é de 6,6. Se 2/3 é a resposta certa para duas dimensões, você deve ser capaz de mostrar que, se tiver cinco pontos, de modo que todas as distâncias euclidianas aos pares sejam pelo menos uma, uma das distâncias euclidianas aos pares será pelo menos . Como você argumenta isso?

\sqrt{1.1}

$\sqrt {1.1}$

Luca Trevisan

Pegue 3 pontos A, B, C em um triângulo equilátero e adicione mais 3 pontos D, E, F, no centro. É claro que você deseja dois de A, B, C em um lado do corte, então digamos que o corte nesses três pontos seja (AB; C). Agora, cada um dos pontos D, E, F deve ir no lado C do corte, de modo que o corte ideal é (AB; CDEF) e a proporção é facilmente verificada como 2/3.

Agora, mova cada um dos pontos D, E, F ligeiramente para longe do centro para formar um pequeno triângulo equilátero. Não importa em que direção, desde que sejam simétricos ao redor do centro. Se você os mover uma distância suficientemente pequena, o corte ideal ainda precisará ser (AB; CDEF). Considere o comprimento desse corte. As arestas (AC, BC) formam 2/3 do comprimento total das arestas (AB, BC, AC). Por simetria, o comprimento total das arestas (AD, AE, AF, BD, BE, BF) é 2/3 do comprimento das arestas (AD, AE, AF, BD, BE, BF, CD, CE, CF ) Mas nenhuma das arestas (DE, EF, DF) está no corte. Portanto, a proporção desse corte é estritamente menor que 2/3.

Você deve otimizar essa construção para encontrar uma configuração em que o corte ideal seja significativamente menor que 2/3. Tentando, entendo que, se você pegar seis pontos dispostos em dois triângulos equilaterais com o mesmo centro, com o menor o tamanho do maior, então o máximo -cut torna-se o peso total em vez de . $(\sqrt{6}-1)/5 \approx .2899$ $.6408$ $2/3$

Peter Shor
fonte

Legal, você está certo! Bem, outra conjectura elegante morde o pó ... Ainda é uma questão em aberto se a constante no plano é maior que 1/2 ou se é possível atingir com clusters , em que . Vou pensar mais sobre isso.

1 - O (k^{- α})

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

k

$k$

α > 1

$\alpha > 1$

Milos Hasan

Meu palpite é que a resposta certa é algo não muito inferior a 0,64, mas não tenho idéia de como mostrar um limite inferior.

precisa