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

12

x1,,xnR2xixj22323

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

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,
1
należy jednak pamiętać, że funkcją wagi jest tutaj KWADRATOWA odległość euklidesowa, co nie jest miarą metryczną.
Suresh Venkat
2
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
2
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
1
@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:

7

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+12)(d+1)2/412d+1d

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
1
@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
1
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,
1
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? 1.1
Luca Trevisan,
7

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 .(61)/5.2899.64082/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. 1O(kα)kα>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,