Maksymalne cięcie w kształcie euklidesa w małych wymiarach

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

Najgorszy przykład, jaki mogę znaleźć, to 3 punkty na równobocznym trójkącie, który osiąga . Zauważ, że losowy podział dałby , ale intuicyjnie wydaje się intuicyjnie, że w niskich wymiarach można skupić się lepiej niż losowo. $\frac 2 3$ $\frac 1 2$

Co się stanie dla maksymalnego k-cięcia dla k> 2? Co powiesz na wymiar d> 2? Czy istnieją ramy umożliwiające udzielenie odpowiedzi na takie pytania? Wiem o nierównościach Cheegera, ale mają one zastosowanie do cięcia rzadkiego (nie maksymalnego) i działają tylko dla zwykłych wykresów.

(Pytanie jest inspirowane problemem grupowania źródeł światła w grafice komputerowej w celu zminimalizowania wariancji).

ds.algorithms graph-algorithms application-of-theory max-cut clustering Milos Hasan
źródło

Istnieje proste przybliżenie 1-2 / k dla Max k-Cut, a dla k> 2 można znaleźć dobre duże cięcie, ale dla k = 2 można zobaczyć www-math.mit.edu/~goemans/PAPERS/maxcut -jacm.pdf i pokrewne tematy, myślę, że jeśli znajdziesz dobre cięcie z dużym prawdopodobieństwem, możesz powiedzieć, że jest cięcie z 2/3 lub nie, przynajmniej zakres możliwości będzie ograniczony.

Saeed,

należy jednak pamiętać, że funkcją wagi jest tutaj KWADRATOWA odległość euklidesowa, co nie jest miarą metryczną.

Suresh Venkat

Domyślam się, że maksymalne cięcie ma ptas, a może nawet algorytm polimeime dla tych przypadków, ale konkretne pytanie jest bardzo interesujące. Czy jasne jest, jakie jest maksymalne cięcie, gdy wierzchołki są równomiernie rozmieszczone wzdłuż cyklu, i że przykładem w tej klasie, który minimalizuje maksymalne cięcie, są trzy równo rozmieszczone wierzchołki? Ponieważ może istnieć argument, który pokazuje, że każdą konfigurację punktów można przekonwertować na konfigurację `` symetryczną '' bez zwiększania stosunku maksymalnego cięcia do masy całkowitej, a zatem może być wystarczające zrozumienie tylko konfiguracji wysoce symetrycznych

Luca Trevisan

Co również dzieje się w jednym wymiarze? Możliwe jest znalezienie konfiguracji, w której maksymalne cięcie wynosi około 2/3 całkowitej masy (jeden punkt to -1, jeden punkt to +1, 4 punkty są bardzo bliskie zeru; całkowita waga wynosi 12, a optymalne wynosi 8). Czy 2/3 to najmniejszy możliwy stosunek maksymalnego cięcia do masy całkowitej w 1 wymiarze?

Luca Trevisan

@Luca: Tak, 1D również nie jest trywialne. Intuicyjnie, stała powinna zbliżać się do 1/2 wraz ze wzrostem wymiaru. W przypadku 2D możemy założyć, że środek ciężkości wynosi (0,0) i że wszystkie punkty mieszczą się w okręgu jednostki. Może istnieć jakiś argument „odpychanie punktu”, który popycha punkty w kierunku koła jednostki, nie zwiększając ciętego ciężaru, co pomogłoby, ale nie mogłem go przypiąć.

Milos Hasan

Odpowiedzi:

Stała ma tendencję do 1/2 wraz ze wzrostem wymiaru. W wymiarach d możesz mieć d + 1 punktów w odległości jeden od siebie, więc suma kwadratu odległości wynosi a maksymalne cięcie to maksymalnie , czyli ułamek całkowitej masy ${d+1 \choose 2}$ $(d+1)^2/4$ $\frac 12 \cdot \frac {d+1}{d}$

Luca Trevisan
źródło

OK, ale dlaczego konfiguracja punktów d + 1 w odległości 1 od siebie stanowi najgorszy przypadek? Wydaje się to prawdopodobne, ale czy to oczywiste? (A dla d = 1 dwa punkty w odległości 1 od siebie wyraźnie nie są najgorszym przypadkiem; podana powyżej konfiguracja 6-punktowa jest gorsza. Czy to możliwe, że d = 1 jest jedynym przypadkiem patologicznym i działa dla d> = 2?)

Milos Hasan

@milos Nie jestem pewien, czy rozumiem. wiemy, że można osiągnąć 0,5, a ten przykład pokazuje, że nie da się lepiej. Nie psuje to jednak przypuszczeń 2/3 dla samolotu.

Suresh Venkat

@Suresh: Naprawdę chciałem udowodnić, że możesz robić lepiej w niskich wymiarach, tzn. Interesuje mnie ciąg rzeczywistych wartości najgorszych stałych dla poszczególnych niskich d.

Milos Hasan

Naprawdę chciałem udowodnić faktyczną lukę między 1/2 a 2/3 dla niskiej d. Miałoby to interesujące konsekwencje, tzn. Że możesz pokonać sumowanie / integrację Monte Carlo (dzieląc swój problem na podproblemy zamiast przypadkowo), jeśli twój problem jest z natury mało wymiarowy (wiele z nich jest).

Milos Hasan,

Chociaż jest to tylko odpowiedź na duże d, pokazuje, jakie trudności mogą pojawić się w analizie przypadku małego d. Załóżmy, że w dwóch wymiarach można mieć pięć punktów, których kwadratowe odległości w parach wynoszą od 1 do 1,1. Wtedy całkowita waga wynosi co najmniej 10, a maksymalne cięcie wynosi co najwyżej 6,6. Jeśli 2/3 jest poprawną odpowiedzią dla dwóch wymiarów, musisz być w stanie wykazać, że jeśli masz pięć punktów takich, że wszystkie pary euklidesowe odległości są co najmniej jeden, jedna z par euklidesowych odległości wynosi co najmniej . Jak to argumentujesz?

\sqrt{1.1}

$\sqrt {1.1}$

Luca Trevisan,

Weź 3 punkty A, B, C na trójkącie równobocznym i dodaj 3 kolejne punkty D, E, F na środku. Oczywiste jest, że chcesz dwa z A, B, C po jednej stronie cięcia, więc powiedzmy, że cięcie w tych trzech punktach to (AB; C). Teraz każdy z punktów D, E, F musi przejść po stronie C cięcia, więc optymalne cięcie to (AB; CDEF), a stosunek można łatwo sprawdzić na 2/3.

Teraz przesuń każdy punkt D, E, F nieco od środka, aby utworzyć mały trójkąt równoboczny. Nie ma znaczenia, w którym kierunku, o ile są symetryczne wokół centrum. Jeśli przesuniesz je na wystarczająco małą odległość, optymalne cięcie nadal musi wynosić (AB; CDEF). Rozważ długość tego cięcia. Krawędzie (AC, BC) stanowią 2/3 całkowitej długości krawędzi (AB, BC, AC). Przy symetrii całkowita długość krawędzi (AD, AE, AF, BD, BE, BF) wynosi 2/3 długości krawędzi (AD, AE, AF, BD, BE, BF, CD, CE, CF ). Ale żadna z krawędzi (DE, EF, DF) nie jest przecięta. Tak więc stosunek tego cięcia jest ściśle mniejszy niż 2/3.

Powinieneś być w stanie zoptymalizować tę konstrukcję, aby znaleźć konfigurację, w której optymalne cięcie jest znacznie mniejsze niż 2/3. Próbując, rozumiem, że jeśli weźmiesz sześć punktów ułożonych w dwa równoboczne trójkąty o tym samym środku, z mniejszym wielkości większego, to max staje się całkowitą wagą zamiast . $(\sqrt{6}-1)/5 \approx .2899$ $.6408$ $2/3$

Peter Shor
źródło

Fajnie, masz rację! Cóż, kolejna elegancka hipoteza gryzie kurz ... Pozostaje jednak otwarte pytanie, czy stała w płaszczyźnie jest większa niż 1/2, czy też można osiągnąć pomocą klastrów , gdzie . Pomyślę o tym więcej.

1 - O (k^{- α})

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

k

$k$

α > 1

$\alpha > 1$

Milos Hasan

Domyślam się, że właściwa odpowiedź jest czymś nie za dużo niższym niż .64, ale nie mam pojęcia, jak przejść do pokazania dolnej granicy.

Peter Shor,