Когда мы нашли лучшие оценки для известных алгоритмов?

16

Существуют ли интересные примеры алгоритмов, которые были опубликованы с проверенными границами, и где позже были опубликованы строго лучшие оценки? Не лучшие алгоритмы с лучшими оценками - очевидно, что это случилось! Но лучший анализ ведет к лучшей оценке существующего алгоритма

Я думал, что умножение матриц было примером этого, но я отговорил себя от этого (возможно, неправильно!) После попытки лучше понять Копперсмит-Виноград и его друзей.

Роб Симмонс
источник
Идеальный пример - умножение матриц. Недавние улучшения на самом деле лучше анализа (Ле Галл, Уильямс и т. Д.).
Lwins
Lwins - я подозревал, что это может быть так, но просмотр некоторых статей заставил меня подумать, что они немного варьируют как алгоритм, так и анализ. Возможно, мне нужно посмотреть глубже.
Роб Симмонс
Это неполный ответ, так как это слух из вторых рук: работая над определением автоматов Buechi ( dl.acm.org/citation.cfm?id=1398627 ), Safra первоначально проанализировала свою конструкцию, чтобы иметь квадратичный показатель. Затем, после записи конструкции, и из-за некоторого недопонимания он получил лучший (оптимальный) показатель . NжурналN
Шаул
Я бы предложил рассмотреть проблемы планирования движения - я чувствую, что там было несколько случаев. Кроме того, IIRC точная сложность симплексного алгоритма (ов?) Была предметом изучения в течение достаточно долгого времени.
Стивен Стадницки
1
Немного отличается, но доказательство существования входа, удовлетворяющего предложений в экземпляре 3SAT, было улучшено до явного алгоритма путем более тщательного анализа. 7м/8
Стелла Бидерман

Ответы:

23

Союз-Найти алгоритм, который Тарьян 1 показал имел сложность Nα(N) , где α(N) является функцией обратного Акерманном, были проанализированы ранее несколькими людьми. Согласно Википедии, это было изобретено Галлером и Фишером 2 , но это кажется неправильным, поскольку у них не было всех компонентов алгоритма, необходимых для его быстрой работы.

Основываясь на кратком просмотре статей, кажется, что алгоритм был изобретен Хопкрофтом и Уллманом 3 , которые дали (неправильную) О(N) временную границу. Затем Фишер 4 нашел ошибку в доказательстве и дал временную привязку О(NжурналжурналN) . Затем Хопкрофт и Ульман 5 дали ограничение по времени O(nlogn) , после чего Тарьян 1 нашел ограничение по времени (оптимальное) O(nα(n)) .

1 Р. Е. Тарьян, «Эффективность хорошего, но не линейного алгоритма объединения множеств» (1975).
2 Б. С. Галлер и М. Дж. Фишер, «Улучшенный алгоритм эквивалентности» (1964).
3 JE Hopcroft и JD Ullman, «Алгоритм слияния линейных списков» (1971).
4 М.Дж. Фишер, «Эффективность алгоритмов эквивалентности» (1972).
5 JE Hopcroft и JD Ullman, "Алгоритмы объединения множеств" (1973).

Питер Шор
источник
2
История этой структуры данных немного неясна для меня, и было бы неплохо исследовать ее. Я просмотрел статью Галлера и Фишера, и она, похоже, описывает структуру данных Disjoint Sets Forest (DSF), но без эвристики критического сжатия пути (PC) и взвешенного объединения (WU). Хопкрофт и Ульман приписывают DSF с ПК и без WU Триттеру, ссылаясь на Кнута. Я не уверен, что DSF с обоими ПК и WU был предложен в опубликованной статье до статьи Хопкрофта и Уллмана, хотя я не удивлюсь, если это так.
Сашо Николов
1
@Sasho: Все это должно быть проверено, так как оно основано на кратких проверках документов. Тарьян приписывает DSF как с ПК, так и с WU Майклу Фишеру в книге «Эффективность алгоритмов эквивалентности» (1972), которая дает времени работы для него. Сканирование бумаги Фишера, он , кажется, приписать алгоритм к Hopcroft и Ульману в «Линейный список слияние алгоритма», но они дают thetas ; ( п ) время выполнения для него, доказательство которой Фишер показывает неверно. Тарджан говорит, что Хопкрофт и Уллман в «Алгоритмах слияния множеств» выкупают себя, давая оценку O ( n log n ) .O(nloglogn)Θ(n)O(nlogn)
Питер Шор
12

Известно, что алгоритм Патури, Пудлака, Сакса и Зейна (PPSZ) для k-SAT имеет время пробега O(1.364n) для 3-SAT с лучшей границей О(1,308N) для формул гарантировано уникальное удовлетворяющее задание. Позже Хертли дал улучшенный анализ, показывающий, что эта улучшенная граница времени выполнения также справедлива для общего случая, таким образом показывая, что PPSZ является лучшим алгоритмом для 3-SAT известно в то время.

Ян Йоханнсен
источник
Это действительно удовлетворительный ответ! Я думаю, что это и примеры Union Find - лучшие примеры того, на что я надеялся.
Роб Симмонс
8

Атака затор упоминает , что анализ общего решето числового поля (применительно к вычислению дискретных логарифмов над Fп ) шаг спуска был tightend см в левом верхнем углу 3 - й странице. Поскольку это единственный шаг, который не может быть предварительно вычислен (если Fп фиксирован), его эффективность сыграла важную роль в их атаке.

Первоначальный анализ , как представляется, в Gordon 92 , где спуск стоило аналогично предвычисления, при Lп(1/3,32/3) . Туже анализ , кажется, от тезиса Barbulescu в , где спуск стоило в Lп(1/3,1,232) , где:

Lп(v,с)знак равноехр((с+о(1))(журналп)v(журналжурналп)1-v)

отметка
источник
1
Очень в духе, спасибо!
Роб Симмонс
6

КО(NК+о(1))О(N2К-2)О(N1,98К+О(1))

Ω(NК)

Примечание: выступление Джейсона Ли (и соответствующие слайды) можно найти на веб-сайте TCS + .


К

Климент С.
источник
4

Алгоритм работы функции для К-сервер был показан (2К-1)-конкурентоспособен Кутсипиасом и Пападимитроу - алгоритм был известен ранее и анализировался только в особых случаях. Предполагается, чтоК-конкурентный.

Чандра Чекури
источник
4

3-Для решения множества было несколько итераций «лучшего анализа» (см. Статьи Фернэу [1] [2] ). Алгоритм, описанный в этой статье, имел несколько произвольных вариантов (например, «выберите ребро» ...), но когда варианты специально выбранный определенным образом, он позволяет проводить более изысканный анализ, в этом и заключается улучшение. И я думаю, что его Приложения в 1дать более точный анализ (подсчет подзадач / подструктур), приводящий к лучшим повторениям и, таким образом, лучшему времени выполнения. Я думаю, что есть много таких примеров в литературе по параметризованной сложности, где добавление еще одной переменной в анализ может привести к улучшению времени выполнения, но я уже несколько лет не играю в эту игру и не могу думать о конкретных момент Существует ряд статей в областях FPT и PTAS, которые появляются при поиске «улучшенного анализа» в названиях статей.

Если указание выбора считается одним и тем же алгоритмом (например, эвристика ранга глубины объединения), то алгоритм Эдмондса-Карпа является «улучшенным анализом» Форда-Фулкерсона, и я полагаю, что существует множество других проблем, которые имеют алгоритмы которые видели улучшения во время выполнения от новых правил выбора.

Затем идет целая куча амортизированного анализа существующих алгоритмов (я думаю, что union-find подходит под это описание, вот еще один https://link.springer.com/article/10.1007/s00453-004-1145-7 )

JimN
источник
Принятие новых решений кажется близким к тому, что я искал, но не совсем так - в некотором смысле более конкретный алгоритм - это «другой алгоритм», но это все еще очень интересные примеры!
Роб Симмонс