Эффективные и простые рандомизированные алгоритмы, где детерминизм сложен

33

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

  • Рандомизированная быстрая сортировка (и связанные геометрические алгоритмы, например, для выпуклых оболочек)
  • Рандомизированный Минцут
  • Проверка полиномиальной идентичности
  • Проблема измерения Кли

Среди них только полиномиальное тестирование идентичности кажется действительно трудным без использования случайности.

Знаете ли вы больше примеров проблем, когда рандомизированное решение является очень элегантным или очень эффективным, а детерминированные решения - нет? В идеале, проблемы должны быть легко мотивированы для непрофессионалов (в отличие, например, от проверки полиномиальной идентичности).

adrianN
источник
10
Другой пример - тестирование на простоту. Вероятностные тесты простоты Миллера – Рабина и Соловая – Штрассена очень просты и эффективны. Это была давняя открытая проблема, чтобы найти эффективный детерминистический критерий первичности, который был решен Агравалом, Каялом и Саксеной. AKS-тест - это детерминированный тест на простоту полиномиального теста. Однако это не так просто и не так эффективно, как вероятностные тесты.
Юрий
8
Рандомизированный отбор (поиск медианы) несколько проще, чем детерминированный. Рандомизированные алгоритмы для приближенного решения упаковывания и покрытия LP быстрее (в худшем случае), чем их детерминированные аналоги ( KY07 , GK95 ). Многие онлайн-проблемы имеют рандомизированные алгоритмы, которые более конкурентоспособны, чем любой детерминированный алгоритм FK91 .
Нил Янг
11
Вычисление объема выпуклого тела в больших измерениях допускает -аппроксимацию посредством рандомизации. Известно, что ни один детерминированный алгоритм не может дать хорошее приближение. Следовательно, рандомизация здесь необходима. (1+ϵ)
Чандра Чекури
5
@ChandraChekuri это хороший комментарий, и он будет еще лучше :)
Suresh Venkat
3
@ChandraChekuri в модели оракула, в противном случаеBPPP
Сашо Николов

Ответы:

36

Сортировка гайки и болты

Следующая проблема была предложена Роулинсом в 1992 году. Предположим, вам дан набор из n гаек и n болтов. Каждый болт соответствует ровно одной гайке, в противном случае гайки и болты имеют разные размеры. Размеры слишком близки, чтобы позволить прямое сравнение между парами болтов или парами гаек. Однако вы можете сравнить любую гайку с любым болтом, пытаясь скрутить их вместе; в постоянное время вы обнаружите, является ли болт слишком большим, слишком маленьким или подходящим для гайки. Ваша задача - выяснить, какой болт подходит для каждой гайки, или, что то же самое, отсортировать гайки и болты по размеру.

Простой вариант рандомизированной быстрой сортировки решает проблему за время с высокой вероятностью. Выберите случайный болт; используйте это, чтобы разделить орехи; используйте подходящую гайку для разделения болтов; и рекурсировать. Однако найти детерминистический алгоритм, который работает даже в o ( n 2 ) , нетривиально. Детерминированные O ( n log n ) -временные алгоритмы были наконец найдены в 1995 году Брэдфордом и независимо друг от друга Комлосом, Ма и Семереди. В обоих случаях оба алгоритма используют варианты параллельной сортировочной сети AKS, поэтому скрытая константа в O ( n log n )O(nlogn)o(n2)O(nlogn)O(nlogn)ограничение по времени довольно большое; скрытая константа для рандомизированного алгоритма равна 4.

  • Нога Алон, Мануэль Блюм, Амос Фиат, Сампат Каннан, Мони Ноар и Рафаил Островский. Подходящие гайки и болты. Proc. 5 числа ACM-SIAM Symp. Дискретные алгоритмы , 690–696, 1994.
  • Нога Алон, Филипп Г. Брэдфорд и Рудольф Флейшер. Подходящие гайки и болты быстрее. Поставить в известность. Proc. Lett. 59 (3): 123–127, 1996.
  • Филипп Дж. Брэдфорд. Подходящие гайки и болты оптимально. Tech. Отчет MPI-I-95-1-025, Институт Макса Планка, 1995 год. Http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-025
  • Филипп Г. Брэдфорд и Рудольф Флейшер. Подходящие гайки и болты быстрее. Proc. Шестой. Int. Symp. Алгоритмы Comput. , 402–408, 1995. Конспект лекций Comput. Sci. 1004.
  • Янош Комлос, Юань Ма и Эндре Семереди. Подходящие гайки и болты за времени. SIAM J. Discrete Math. 11 (3): 347–372, 1998.O(nlogn)
  • Грегори Дж. Э. Роулинс. По сравнению с чем? : Введение в анализ алгоритмов . Информатика Пресс / WH Freeman, 1992.
Jeffε
источник
2
Это прекрасный пример, но это проблема оракула. Есть ли способ удалить оракула из него?
Питер Шор
Есть ссылка на газету «Семереди 98»? Как это сложно? Параллельно сравните каждый болт с уникальной гайкой и расположите каждую пару в отсортированном порядке; удаление согласованных элементов. В log (n) шагах объедините отсортированные последовательности nbnbnbnbnb, выбивая совпадения по мере их появления. РЕДАКТИРОВАТЬ: Да, несопоставимость строк nnn и bbbb раздражает на этапе объединения.
Чад Brewbaker
@ChadBrewbaker Предположим, что в каждой паре, кроме одной, болт меньше, чем гайка. (Да, это возможно.) Что делает ваш алгоритм? Другими словами, «раздражает» = «вся проблема».
Джефф
Я искал газету Семереди и вслух размышлял, как это тяжело. Да, я согласен, что подход, основанный на слиянии, нетривиален; но работы Вишкина о связности параллельных графов оставляют интуитивное ощущение, что это не невозможно.
Чад Brewbaker
При каждом сравнении гайки и болта вы получаете направленное ребро, добавленное к графику или совпадение, которое удаляет обе вершины. Цель состоит в том, чтобы объединить связанные компоненты таким образом, чтобы они объединяли все совпадения между ними с линейным объемом работы и сохраняли размер хранения ребер в связанном компоненте, ограниченный линейным пространством.
Чад Brewbaker
17

Если вы не просто говорите о поли-времени, а скорее смотрите на многие модели вычислений, которые мы изучаем, везде есть примеры:

В Logspace: Ненаправленное подключение ST (в RL с 1979 года и в L только с 2005 года)

В NC: Нахождение идеального соответствия в двудольном графе параллельно (в RNC и до сих пор неизвестно, что в NC)

В интерактивных доказательствах: детерминированные дают NP, в то время как рандомизированные могут делать PSPACE. Связанный: проверка доказательства детерминистически требует рассмотрения всех доказательств, в то время как доказательства PCP позволяют проверять только постоянное число битов.

В алгоритмическом проектировании механизмов: множество рандомизированных механизмов достоверного приближения без детерминированного аналога.

В сложности коммуникации: функция равенства требует линейной связи детерминистически, но логарифмически (или, в зависимости от точной модели, константы) связь случайно

В деревьях решений: оценка дерева и / или дерева требует линейных запросов детерминистически, но намного меньше с рандомизацией. Это по сути эквивалентно альфа-бета-обрезке, которая дает рандомизированный сублинейный алгоритм для оценки игрового дерева.

В потоковых моделях, моделях распределенных вычислений: см. Предыдущие ответы.

Ноам
источник
12

Большинство потоковых алгоритмов

В потоковой модели вычислений ( AMS , book ) алгоритм обрабатывает онлайн-последовательность обновлений и ограничивается только сублинейным пространством. В любой момент времени алгоритм должен иметь возможность ответить на запрос.

tit[n]Dm=|{it:t=1m}|mΩ(n)O(logn)O(1ϵ2+logn)1±ϵ

Сашо Николов
источник
8

nΔmin(Ω(logΔ),Ω(logn))

u

  1. u1/dudu>0udu=0u
  2. uu
  3. v

O(logn)O(n1/logn)


[1] Майкл Луби: простой параллельный алгоритм для задачи о максимальном независимом множестве. SIAM J. Comput. 15 (4): 1036-1053 (1986) http://dx.doi.org/10.1137/0215074

[2] Алессандро Панконези, Аравинд Шринивасан: О сложности разложения распределенных сетей. J. Алгоритмы 20 (2): 356-374 (1996) http://dx.doi.org/10.1006/jagm.1996.0017

[3] Фабиан Кун, Томас Москиброда, Роджер Ваттенхофер: Локальные вычисления: нижние и верхние границы. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

Питер
источник
Недавний алгоритм (на PODC 2013), основанный на биологических системах, обеспечивает такую ​​же производительность, что и Luby, благодаря использованию простого механизма локальной обратной связи. arxiv.org/abs/1211.0235
Андраш Саламон,
6

Выборы лидера в анонимном кольце процессов

1

Есть простой аргумент (например, [1]), что для анонимного кольца не существует детерминированного алгоритма выбора лидера.

Модель: мы предполагаем, что вычисления продвигаются в синхронных раундах, где в каждом раунде каждый процесс выполняет некоторые локальные вычисления, отправляет сообщения своим соседям по кольцу и получает сообщения от своих соседей.

Ar01

r0rArrr+1A

An[1,n4]


[1] Дана Англуин: Локальные и глобальные свойства в сетях процессоров (расширенная аннотация). STOC 1980: 82-93. http://doi.acm.org/10.1145/800141.804655

Питер
источник
6

Проблема большинства в модели запросов.

nij

n/2O(n)

O(n)

FRK Chung, RL Graham, J. Mao и AC Yao. Забывчивые и адаптивные стратегии для задач большинства и множественности, Proc. COCOON 2005 , с. 329–338.

Jagadish
источник