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).

— 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,