Другие применения усиления разветвления Каргера-Штейна?

27

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

Алгоритм Каргера и Стейна представляет собой уточнение более раннего алгоритма Каргера, который итеративно сжимает случайные ребра, пока граф не имеет только две вершины; этот простой алгоритм выполняется за времени и возвращает минимальное сокращение с вероятностью , где - количество вершин во входном графе. Уточненный «Алгоритм рекурсивного сокращения» итеративно сжимает случайные ребра, пока число вершин не падает с до , рекурсивно вызывает себя дважды на оставшемся графе и возвращает меньшее из двух результирующих разрезов. Простая реализация усовершенствованного алгоритма выполняется вO(n2)Ω(1/n2)nnn/2O(n2logn)время и возвращает минимальное сокращение с вероятностью . (Существуют более эффективные реализации этих алгоритмов и более рандомизированные алгоритмы.)Ω(1/logn)

Какие другие рандомизированные алгоритмы используют аналогичные методы усиления ветвления? Я особенно заинтересован в примерах , которые не (очевидно) включают сокращение графика.

Jeffε
источник
2
Хороший вопрос, Джефф!
Суреш Венкат
Это дурачок?
Джефф
не уверен, что ты имеешь в виду
Суреш Венкат
Кроме того, что бы вы рассмотрели в качестве примера усиления ветвления?
Суреш Венкат
2
швырка также является значком на этом сайте, который, безусловно, не относится к вашему вопросу, @JeffE!
Лев Рейзин

Ответы:

5

@JeffE, вот статья, которая считает минимальные весовые циклы на графике. Насколько я помню, это было определенно вдохновлено техникой / результатом Каргера, и это было забавное доказательство. Надеюсь, это поможет с обучением.

V Vinay
источник
Эта статья не учитывает количество циклов минимального веса на графике. Вместо этого он дает ограничение на число циклов, вес которых не более чем на некоторое постоянное кратное весу цикла минимального веса.
Тайсон Уильямс