Аддитивные комбинаторные приложения в разработке алгоритмов

12

Я читаю обзоры Тревизана и Ловетта о применении аддитивного комбинаторика в TCS. Большинство этих приложений подпадают под сложность вычислений , например, нижние границы. Интересно, нашла ли аддитивная комбинаторика применение в разработке алгоритмов ?

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

user32373
источник
Я думаю, что «принятие» для этого типа вопросов не имеет смысла, так как цель состоит в составлении списка соответствующих указателей. Но я согласился с Райаном, так как указанный результат определенно является тем типом соединений, которые я искал: использование аддитивной комбинаторики явно заложено в разработку алгоритма, и решение интригует из-за того, что BSG не удалось взломать печально известный 3SUM.
user32373

Ответы:

17

Тимоти Чан и Моше Левенштейн имеют доклад о 3SUM и связанных с ним проблемах в предстоящей STOC, в котором применяется эффективная версия теоремы BSG из аддитивной комбинаторики для решения вариантов 3SUM быстрее, чем n ^ 2 раз.

Смотрите эту ссылку на документы Чана .

Райан Уильямс
источник
3SAT
1
3SAT3SAT1.308n
8

Алгоритм DC3 для вычисления массива суффиксов использует преимущества аддитивной комбинаторики. Он использует покрытия различий в ключевой части алгоритма. Идеи очень крутые и доступные. Алгоритм также имеет отличную производительность на практике и широко преподается.

GSgGs,tSg=stGn

Вот цитата:

Юха Кярккяйнен, Питер Сандерс, Стефан Буркхардт. Линейная работа Суффикс Массив Строительство . Журнал ACM, 2006.

DW
источник
5

Если вы включите тестирование в разработку алгоритмов, Самородницкий использует аддитивную комбинаторику, чтобы показать, что линейные преобразования эффективно тестируются [здесь] .

Manu
источник