Outras aplicações da amplificação de ramificação Karger-Stein?

27

Acabei de ensinar o algoritmo de mincut aleatório Karger-Stein na minha classe de algoritmos de pós-graduação. Esta é uma verdadeira jóia algorítmica , então eu não posso não ensiná-lo, mas ele sempre me deixa frustrado, porque eu não sei quaisquer outras aplicações da técnica principal. (Portanto, é difícil atribuir tarefas de casa que direcionem o assunto para casa.)

O algoritmo de Karger e Stein é um refinamento de um algoritmo anterior de Karger, que contrata arestas aleatórias iterativamente até que o gráfico tenha apenas dois vértices; esse algoritmo simples é executado no tempo e retorna um corte mínimo com probabilidade Ω ( 1 / n 2 ) , onde n é o número de vértices no gráfico de entrada. O refinado "Algoritmo de Contração Recursiva" contrai iterativamente arestas aleatórias até que o número de vértices caia de n para n / O(n2)Ω(1/n2)nn , chama-se recursivamenteduas vezesno gráfico restante e retorna o menor dos dois cortes resultantes. Uma implementação direta do algoritmo refinado é executada no tempoO(n2logn)e retorna um corte mínimo com probabilidadeΩ(1/logn). (Existem implementações mais eficientes desses algoritmos e melhores algoritmos aleatórios.)n/2O(n2registron)Ω(1/registron)

Que outros algoritmos randomizados usam técnicas de amplificação de ramificação semelhantes? Estou especialmente interessado em exemplos que não (obviamente) envolvem cortes gráfico.

Jeffε
fonte
2
Boa pergunta, Jeff!
Suresh Venkat
Isso é uma erva daninha?
Jeffε
Não sei o que você quer dizer #
Suresh Venkat
Além disso, o que você consideraria um exemplo de amplificação ramificada?
Suresh Venkat
2
tumbleweed também é um emblema neste site, o que certamente não se aplica à sua pergunta, @JeffE!
Lev Reyzin

Respostas:

5

@ Jeff, Aqui está um artigo que conta ciclos mínimos de peso em um gráfico. Tanto quanto me lembro, foi definitivamente inspirado pela técnica / resultado de Karger e foi uma prova divertida. Espero que isso ajude com o ensino.

V Vinay
fonte
Este artigo não conta o número de ciclos de peso mínimo em um gráfico. Em vez disso, fornece um limite para o número de ciclos cujo peso é no máximo algum múltiplo constante do peso do ciclo de peso mínimo.
Tyson Williams