Я только что преподавал рандомизированный алгоритм сокращений по методу Каргера-Стейна в своем выпускном классе алгоритмов. Это настоящая алгоритмическая жемчужина , поэтому я не могу ее не преподавать, но она всегда расстраивает меня, потому что я не знаю других применений основной техники. (Таким образом, трудно назначить домашнюю работу, которая заставляет точку домой.)
Алгоритм Каргера и Стейна представляет собой уточнение более раннего алгоритма Каргера, который итеративно сжимает случайные ребра, пока граф не имеет только две вершины; этот простой алгоритм выполняется за времени и возвращает минимальное сокращение с вероятностью , где - количество вершин во входном графе. Уточненный «Алгоритм рекурсивного сокращения» итеративно сжимает случайные ребра, пока число вершин не падает с до , рекурсивно вызывает себя дважды на оставшемся графе и возвращает меньшее из двух результирующих разрезов. Простая реализация усовершенствованного алгоритма выполняется ввремя и возвращает минимальное сокращение с вероятностью . (Существуют более эффективные реализации этих алгоритмов и более рандомизированные алгоритмы.)
Какие другие рандомизированные алгоритмы используют аналогичные методы усиления ветвления? Я особенно заинтересован в примерах , которые не (очевидно) включают сокращение графика.
Ответы:
@JeffE, вот статья, которая считает минимальные весовые циклы на графике. Насколько я помню, это было определенно вдохновлено техникой / результатом Каргера, и это было забавное доказательство. Надеюсь, это поможет с обучением.
источник