Tasowanie tokenów na wykresie za pomocą lokalnych zamian

Niech będzie nieregularnym połączonym wykresem, którego stopień jest ograniczony. Załóżmy, że każdy węzeł zawiera unikalny token. $G= (V, E)$

Chcę równomiernie tasować tokeny między wykresami, używając tylko lokalnych zamian (tj. Wymiany tokenów między dwoma sąsiadującymi węzłami)? Czy znana jest dolna granica tego problemu?

Jedyny pomysł, jaki miałem, to użyć wyniku losowego marszu, a następnie zobaczyć, ile zamian potrzebuję do „symulacji” efektu przypadkowych spacerów transportujących tokeny na wykresie.

ds.algorithms random-walks dc.distributed-comp Sylvain Peyronnet
źródło

Jakiego rodzaju dolnej granicy szukasz? Łączna liczba swapów? Liczba równoległych rund (tzn. W 1 kroku możesz zamienić wzdłuż wszystkich krawędzi dopasowania w

)? Dolna granica jako funkcja

? Czy wszystkie węzły znają topologię

(i mogą odpowiednio dostosować swoje zachowanie), czy szukasz stałej strategii, którą można zastosować na dowolnym wykresie?

G

$G$

| V |

$|V|$

d i a m (G)

$diam(G)$

G

$G$

Jukka Suomela,

Przepraszam, powinienem był być bardziej konkretny. Celem jest zaprojektowanie metody rozpowszechniania danych dla sieci czujników, która pozwoli uniknąć problemów związanych z metodami opartymi na przypadkowych spacerach (zasadniczo utrata informacji z powodu zderzenia kilku tokenów w tym samym węźle). Jestem więc zainteresowany całkowitą liczbą swapów (da to liczbę wiadomości krążących w sieci) i liczbą rund (aby z grubsza oszacować czas konwergencji). LB jako funkcja

jest w porządku, a węzły nie są świadome topologii (niestety).

V

$V$

Sylvain Peyronnet,

Odpowiedzi:

Załóżmy, że twój wykres jest ścieżką. Myślę, że ten problem staje się równoważny sortowaniu losowej sekwencji liczb w tablicy przez zamianę sąsiednich wpisów. Nawet wszystkie węzły są świadome topologii, dostajesz ^ 2 dolną granicę liczby zamian (nie może to zrobić lepiej niż sortowanie bąbelkowe, które jest n ^ 2 nawet przy losowym wejściu).

Lew Reyzin
źródło

W przypadku ścieżki proces zamiany z prawdopodobieństwem 1/2 miesza się w

, co udowodnili Benjamini, Berger i Hoffman (to przypuszczali Diaconis i Ram). Więc mój LB jest również funkcją stopnia, o którym myślę ...

O (n^{2})

$O(n^2)$

Sylvain Peyronnet

Ten LB mówi, że nie możesz poprawić algorytmu, nawet jeśli możesz wybrać swapy ... ale prawda, myślę, że problem może być łatwiejszy, gdy rośnie (średni?) Stopień.

Lew Reyzin

Zaplanuję kilka symulacji, aby zobaczyć, jak potoczy się sytuacja, gdy stopień się zwiększy.

Sylvain Peyronnet,

W rzeczywistości wygląda na to, że ten LB (z pewną modyfikacją) utrzyma się, nawet jeśli dwa końce ścieżki mają duże kliki - jak w 2 klikach na n / 4 połączonych ścieżką n / 2 węzłów. Teraz średni stopień to O (n), ale nadal nie możesz pokonać n ^ 2. Być może musimy narzucić minimalny stopień?

Lew Reyzin

Tak, potrzebujemy minimalnego stopnia :(

Sylvain Peyronnet

Chciałbym zwrócić uwagę na związek między tym problemem a sieciami sortującymi. Na przykład, jeśli wykres jest ścieżką, to trywialna sieć sortująca z liniową głębokością pokazuje również, że można uzyskać dowolną permutację w liniowej liczbie rund. Ponadto jest to ścisłe, ponieważ po prostu zamiana elementów w punktach końcowych ścieżki wymaga liniowej liczby rund.

Sieci sortujące AKS pokazują, że istnieją wykresy, na których można uzyskać dowolną permutację w logarytmicznej liczbie rund. W przypadku wykresów siatkowych patrz np . Notatki z wykładu .

(Oczywiście sortowanie i tasowanie są różnymi problemami, ale wiele górnych i dolnych granic jest powiązanych. Np. Wybierz losowe etykiety i sortuj według etykiet.)

Jukka Suomela
źródło

Dzięki za wskaźnik. Będę kopać w tym kierunku, może nie jest to coś, czego potrzebuję (nie jestem pewien, czy mam dobry typ wykresu), ale z pewnością będzie to coś, co wykorzystam wcześniej czy później!

Sylvain Peyronnet,