Перестановка токенов на графе с использованием локальных свопов

Пусть нерегулярный связный граф, степень которого ограничена. Предположим, что каждый узел содержит уникальный токен. $G= (V, E)$

Я хочу равномерно перетасовать токены среди графа, используя только локальные перестановки (т.е. обмен токенами между двумя соседними узлами)? Известна ли нижняя граница для этой проблемы?

Единственная идея, которая у меня возникла, - это использовать результат случайного блуждания, а затем посмотреть, сколько свопов мне нужно, чтобы «смоделировать» эффект случайных блужданий, переносящих токены на график.

ds.algorithms random-walks dc.distributed-comp Сильвен Пейроннет
источник

Какую нижнюю границу вы ищете? Общее количество свопов? Количество параллельных раундов (т. Е. За 1 шаг вы можете поменять местами все совпадающие ребра в )? Оценка снизу как функция от, ? Все ли узлы знают топологию (и могут ли они соответствующим образом адаптировать свое поведение), или вы ищете фиксированную стратегию, которую можно применить на любом графике?

G

$G$

| V |

$|V|$

d i a m (G)

$diam(G)$

G

$G$

Юкка Суомела

Я должен был быть более конкретным, извините. Цель состоит в том, чтобы разработать метод распространения данных для сенсорных сетей, который позволит избежать проблем, связанных с методами случайных блужданий (по существу, потеря информации из-за столкновения нескольких токенов в одном узле). Поэтому меня интересует общее количество перестановок (это даст количество сообщений, циркулирующих в сети) и количество раундов (чтобы получить приблизительную оценку времени конвергенции). LB как функция - это нормально, а узлы не знают топологию (к сожалению).

V

$V$

Сильвен Пейроннет

Ответы:

Предположим, ваш график был путем. Я думаю, что тогда эта проблема становится эквивалентной сортировке случайной последовательности чисел в массиве путем замены соседних записей. Даже из всех узлов с учетом топологии вы получаете нижнюю границу ^ 2 для числа перестановок (не может быть лучше, чем сортировка пузырьком, которая равна n ^ 2 даже на случайном входе).

Лев Рейзин
источник

В случае пути процесс обмена с вероятностью 1/2 смешивается в , это было доказано Бенджамини, Бергером и Хоффманом (это было предположено Диаконисом и Рамом). Так что мой LB также является функцией степени, которую я предполагаю ...

O (n^{2})

$O(n^2)$

Сильвен Пейроннет

Этот LB говорит, что вы не можете улучшить алгоритм, даже если вы можете выбрать свои свопы ... но верно, я думаю, что проблема может стать легче, когда (средняя?) Степень возрастает.

Лев Рейзин

Я запланирую некоторые симуляции, чтобы увидеть, как все пойдет, когда степень растет.

Сильвен Пейроннет

На самом деле, похоже, что этот LB (с некоторой модификацией) будет удерживаться, даже если два конца пути имеют большие клики - как в 2 кликах на n / 4, соединенных путем n / 2 узлов. Теперь средняя степень равна O (n), но вы все равно не можете победить n ^ 2. Возможно, нам нужно ввести минимальную степень?

Лев Рейзин

Да, нам нужна минимальная степень :(

Сильвен Пейроннет

Я хотел бы указать на связь между этой проблемой и сетью сортировки. Например, если ваш граф представляет собой путь, то тривиальная сеть сортировки по линейной глубине также показывает, что вы можете получить любую перестановку в линейном количестве раундов. Более того, это сложно, так как для простой замены элементов в конечных точках пути требуется линейное число раундов.

Сортировочные сети AKS показывают, что существуют графики, в которых вы можете получить любую перестановку в логарифмическом количестве раундов. Для случая графиков сетки, см., Например, эти примечания к лекции .

(Конечно, сортировка и перемешивание - разные проблемы, но многие верхние и нижние границы связаны. Например, выбирайте случайные метки и сортируйте по меткам.)

Юкка Суомела
источник

Спасибо за указатель. Я буду копать в этом направлении, может быть, это не то, что мне нужно здесь (я не уверен, что у меня есть хороший тип графиков), но это, безусловно, будет то, что я буду использовать рано или поздно!

Сильвен Пейроннет