Obliczanie odległości z przybliżeniem mniejszym niż 2 na ogólnych wykresach?

Biorąc pod uwagę ważony niekierowany wykres z krawędziami $m = o(n^2)$ , chciałbym obliczyć odległości aproksymacji mniejsze niż 2 między dowolną parą wierzchołków. Oczywiście chciałbym użyć przestrzeni subkwadratowej i podliniowego czasu zapytania.

Jestem świadomy wyniku Zwicka, który wykorzystuje mnożenie macierzy, ale jestem ciekawy, czy znane są algorytmy kombinatoryczne dla tego problemu?

ds.algorithms graph-algorithms Siddhartha
źródło

Cześć @Siddhartha, przepraszam, jeśli to głupie pytanie: wynik Zwicka wydaje się używać przestrzeni kwadratowej, czy to prawda?

Hsien-Chih Chang 之之

Czy dozwolony jest również błąd addytywny?

Hsien-Chih Chang 之之

@ Hsien-ChihChang 張顯之 - interesowały mnie wyniki tylko w przybliżeniu multiplikatywnym. Przypadek aproksymacji addytywnej może być interesujący sam w sobie - wydaje mi się, że łatwiej jest w przypadku gęstych wykresów. Można użyć klucza i uzyskać przybliżenie addytywne dla wystarczająco gęstych wykresów. W przypadku rzadkich wykresów, o ile mi wiadomo, klucze nie pomogłyby.

Siddhartha,

Czy następujący argument nie działa? Rozważ dowolny wykres

wierzchołkami i krawędziami

. Weź pod uwagę wszystkie ciężary krawędzi jako

. każda wyrocznia odległości, która może dokonać dokładniejszego przybliżenia niż

, może być wykorzystana do podjęcia decyzji dla każdej możliwej krawędzi, niezależnie od tego, czy jest ona na wykresie. Ale to oczywiście oznacza, że taka wyrocznia odległości musi wykorzystywać bity

. Nie? (Argument jest nieco zawiły, ale powinien być poprawny.) (Formalnie liczba bitów to

G

$G$

n

$n$

m

$m$

1

$1$

2

$2$

Ω (m)

$\Omega(m)$

, gdzie

\log_{2} (\binom{N}{m})

$\log_2 \binom{N}{m}$

. Jest to

N = (\binom{n}{2})

$N=\binom{n}{2}$

\geq m \log_{2} (N / m)

$\geq m \log_2 (N/m)$

Sariel Har-Peled,

Dzięki Sariel - możliwe jest uzyskanie dolnej granicy

ale nie mam nic przeciwko. Chciałbym mieć jedynie przestrzeń subkwadratową i sublinearny czas zapytania. W przypadku wykresów

krawędziach

dolna granica

nie mówi nic o problemie - prawda?

Ω (m)

$\Omega(m)$

m = o (n^{2})

$m = o(n^2)$

Ω (m)

$\Omega(m)$

Siddhartha,

Odpowiedzi:

O ile mi wiadomo, nie ma opublikowanego wyniku obliczania odległości aproksymacji mniejszych niż 2 w przestrzeni subkwadratowej i podliniowym czasie zapytania. W celu szybkiego wyszukiwania przybliżonych odległości warto przyjrzeć się wynikom i referencjom w „Szybszych algorytmach dla wszystkich par przybliżonych najkrótszych ścieżek” autorstwa Baswany i Kavithy (wersja czasopisma ich pracy FOCS ma dobry przegląd powiązanych prac); żadne z nich nie osiąga przestrzeni subkwadratowej.

W celu kompaktowego pobierania przybliżonych odległości warto przyjrzeć się wynikom i odnośnikom w dwóch powyższych artykułach. [Jako uzupełnienie odpowiedzi Gabora, słowo przestrogi: uważaj na pojęcie rzadkości w powyższych dokumentach - dla przybliżenia wykres mówi się, że jest rzadki, jeśli , jak prawdopodobnie wiem już]. $2$ $m = o(n^2)$

Jak zauważyła Sariel w jednym z powyższych komentarzy, naturalną dolną granicą przestrzeni dla obliczania odległości aproksymacyjnych mniejszych niż jest , to znaczy liniowy w wielkości wykresu. Jeśli czas zapytania nie jest ograniczony, to dolnej granicy nie można poprawić (trywialnie, można użyć algorytmu najkrótszej ścieżki po prostu przechowując wykres). Dla stałego czasu zapytania znam dwie dolne granice. Po pierwsze, Patrascu i Roddity mieli pewne warunkowe dolne granice w swoim dokumencie FOCS 2010, które dotyczą aproksymacji mniejszej niż . Po drugie, Sommer i in. glin. miał pewne dolne granice dla bardzo rzadkich wykresów. Nie znam żadnych innych (nietrywialnych) dolnych granic. $2$ $\Omega(m)$ $2$

Jeśli chodzi o górne granice, wyniki z powyższych prac nie wydają się uogólniać do przybliżenia mniejszego niż . Ostatnio poczyniliśmy postępy w tym problemie. Artykuł powinien wkrótce pojawić się w ArXiv, ale jeśli chcesz, wyślij mi e-mail, a chętnie podzielę się nim. $2$

Mam nadzieję że to pomoże.

~ Rachit Agarwal

Rachit
źródło

Być może zainteresuje Cię dokument INFOCOM 2011 Rachita Agarwala:

Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled Przybliżone zapytania o odległość i kompaktowe trasy na rzadkich wykresach, IEEE INFOCOM 2011

Z streszczenia:

$\Theta(\log n)$ $O(n^{3/2})$ $O(\sqrt{n})$

Zauważ, że ich wyrocznia odległości jest tylko dla rzadkich wykresów, ale logarytmiczne ograniczenie stopnia wydaje się prawdopodobne. Dodano premię, algorytm działa również w przypadku wykresów ważonych.

Gabor Retvari
źródło

Możesz także rzucić okiem

Pătraşcu, Roditty, Distance Oracles Beyond the Thorup - Zwick Bound , FOCS 2010

$O(n^{5/3})$

zotachidil
źródło

Dzięki! Artykuł z Agrawal i Mihai nie wydaje się mówić o przybliżeniu „mniej niż” 2, chyba że coś przeoczyłem.

Siddhartha,

Nie jest, ale może dać ci wyobrażenie o tym, jak uzyskać kompromis w celu poprawy odcinka.

zotachidil