Baralhar de tokens em um gráfico usando trocas locais

Seja um grafo conectado não regular cujo grau é delimitado. Suponha que cada nó contenha um token exclusivo. $G= (V, E)$

Eu quero embaralhar uniformemente os tokens no gráfico usando apenas swaps locais (ou seja, troca dos tokens entre dois nós adjacentes)? Existe um limite inferior conhecido para esse problema?

A única idéia que tive foi usar um resultado de caminhada aleatória e, então, ver quantos swaps eu preciso "simular" o efeito de caminhadas aleatórias transportando tokens no gráfico.

ds.algorithms random-walks dc.distributed-comp Sylvain Peyronnet
fonte

Que tipo de limite inferior você está procurando? Número total de swaps? Número de rodadas paralelas (ou seja, em uma etapa você pode trocar ao longo de todas as arestas de uma correspondência em

)? Limite inferior em função de

? Todos os nós conhecem a topologia de

(e podem adaptar seu comportamento de acordo), ou você está procurando uma estratégia fixa que possa ser aplicada em qualquer gráfico?

G

$G$

| V |

$|V|$

d i a m (G)

$diam(G)$

G

$G$

Jukka Suomela 18/08/10

Eu deveria ter sido mais específico, desculpe. O objetivo é projetar um método de disseminação de dados para redes de sensores que evitem problemas de métodos baseados em caminhadas aleatórias (essencialmente perda de informações devido a vários tokens colidindo no mesmo nó). Portanto, estou interessado no número total de swaps (isso fornecerá o número de mensagens circulando na rede) e o número de rodadas (para ter uma estimativa aproximada do tempo de convergência). um LB como uma função de

é bom e os nós não têm conhecimento da topologia (infelizmente).

V

$V$

Sylvain Peyronnet

Respostas:

Suponha que seu gráfico seja um caminho. Acho que esse problema se torna equivalente a classificar uma sequência aleatória de números em uma matriz trocando entradas adjacentes. Mesmo todos os nós reconhecem a topologia, você obtém um limite inferior de ^ 2 no número de swaps (não pode fazer melhor do que a classificação de bolhas que é n ^ 2 mesmo em uma entrada aleatória).

Lev Reyzin
fonte

O (n^{2})

$O(n^2)$

Este LB diz que você não pode melhorar o algoritmo, mesmo que possa escolher seus swaps ... mas, certo, acho que o problema pode ficar mais fácil à medida que o grau (médio?) Aumenta.

Lev Reyzin

Vou agendar algumas simulações para ver como as coisas vão quando o grau está crescendo.

Sylvain Peyronnet

Na verdade, parece que esse LB (com algumas modificações) será válido, mesmo que as duas extremidades do caminho tenham grandes panelinhas - como em duas panelinhas no n / 4 conectadas por um caminho de n / 2 nós. Agora, o grau médio é O (n), mas você ainda não consegue vencer n ^ 2. Talvez precisemos impor um grau mínimo?

Lev Reyzin

Sim, precisamos de um grau mínimo :(

Sylvain Peyronnet

Eu gostaria de salientar a relação entre esse problema e as redes de classificação. Por exemplo, se seu gráfico for um caminho, a rede trivial de classificação de profundidade linear também mostrará que você pode obter qualquer permutação no número linear de rodadas. Além disso, isso é apertado, pois simplesmente trocar os elementos nos pontos finais do caminho requer um número linear de rodadas.

As redes de classificação da AKS mostram que existem gráficos nos quais você pode obter qualquer permutação no número logarítmico de rodadas. Para o caso de gráficos de grade, consulte, por exemplo, estas notas de aula .

(É claro que classificar e embaralhar são problemas diferentes, mas muitos limites superior e inferior estão relacionados. Por exemplo, escolha rótulos aleatórios e classifique por rótulos.)

Jukka Suomela
fonte

Obrigado pelo ponteiro. Vou cavar nessa direção, talvez não seja o que preciso aqui (não tenho certeza se tenho o bom tipo de gráfico), mas certamente será algo que usarei mais cedo ou mais tarde!

Sylvain Peyronnet