Рандомизированные алгоритмы с использованием стека

11

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

Чтобы дать вам больше контекста, я ищу список проблем, похожих на те, что описаны в статье SivaKumar . Обратите внимание, что SivaKumar использовал псевдослучайный генератор Нисана, чтобы дерандомизировать эти проблемы.

Шива Кинтали
источник
3
Не могли бы вы привести примеры рекурсивных рандомизированных алгоритмов, которые не используют существенный стек? Как насчет рандомизированного алгоритма Вельцля для минимальных вмещающих эллипсоидов с глубиной рекурсии O (d), где d - размерность пространства.
Per Vognsen
Вы должны сделать это ответом!
Суреш Венкат

Ответы:

6

Как указывает Пер Вогнсен, и в более общем смысле, существует множество геометрических алгоритмов, которые работают следующим образом: выбирают случайную выборку и рекурсивно запускают выборку и другие производные от нее структуры. Рандомизированный алгоритм Кларксона для линейного программирования, а также ряд Зейделя и, в действительности, ряд Матусека-Шарира-Вельцля, о котором упоминает Пер, работают именно таким образом, и парадигма Кларксона распространяется и на другие ситуации, когда вы строите некую разновидность резания или эпсилон-сеть и рекурсивную ,

К сожалению, вы вряд ли получите новый результат от этого, потому что есть оптимальные дерандомизации этих алгоритмов, благодаря работе Matousek и Chazelle. Статья Шазель является хорошим ориентиром для этой работы и предыдущей работы Матусека. Но это может быть хорошей проверкой вашего метода: трудно было придумать эти дерандомизации, и если ваш метод обеспечивает подход черного ящика, начинающийся с (более простого) рандомизированного алгоритма, это было бы здорово.

ps это, пожалуй, самый скучный пример из всех возможных, но работает ли ваш метод на быстрой сортировке или на любом из методов рандомизированного нахождения медианы?

Суреш Венкат
источник
Да. Мой подход - метод черного ящика. Похоже, он не работает с быстрой сортировкой или рандомизированными методами поиска медианы. Я пойду через газету Chazelle. Спасибо.
Шива Кинтали
6

Как насчет рандомизированного алгоритма Вельцля для минимальных вмещающих эллипсоидов? Он имеет глубину рекурсии O (d), где d - размерность пространства.

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

Пер Вогсен
источник
Я не знаю об этом алгоритме. Спасибо за указание. Допустим, стек не важен, если удаление стека приводит к незначительному увеличению времени выполнения. У меня нет примера рекурсивных рандомизированных алгоритмов, которые не используют существенное использование стека.
Шива Кинтали
4

Более быстрая версия алгоритма min-cut действительно очень рекурсивна. Смотрите рисунок 2.5 здесь , или любой стандартный учебник по рандомизированным алгоритмам.

Сариэль Хар-Пелед
источник
Это также отличный пример
Суреш Венкат