Я читаю обзоры Тревизана и Ловетта о применении аддитивного комбинаторика в TCS. Большинство этих приложений подпадают под сложность вычислений , например, нижние границы. Интересно, нашла ли аддитивная комбинаторика применение в разработке алгоритмов ?
Мотивация для моего вопроса заключается в следующем: хотя связь между аддитивной комбинаторикой и сложностью кажется несколько естественной, мне любопытно посмотреть, как алгебраическая структура, раскрытая аддитивной комбинаторикой, может быть использована при разработке эффективных алгоритмов, если таковые имеются. Указатели на литературу будут оценены.
Ответы:
Тимоти Чан и Моше Левенштейн имеют доклад о 3SUM и связанных с ним проблемах в предстоящей STOC, в котором применяется эффективная версия теоремы BSG из аддитивной комбинаторики для решения вариантов 3SUM быстрее, чем n ^ 2 раз.
Смотрите эту ссылку на документы Чана .
источник
Алгоритм DC3 для вычисления массива суффиксов использует преимущества аддитивной комбинаторики. Он использует покрытия различий в ключевой части алгоритма. Идеи очень крутые и доступные. Алгоритм также имеет отличную производительность на практике и широко преподается.
Вот цитата:
Юха Кярккяйнен, Питер Сандерс, Стефан Буркхардт. Линейная работа Суффикс Массив Строительство . Журнал ACM, 2006.
источник
См. Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J. (2015, февраль). Сумма подмножества в отсутствие концентрации. В EW Mayr, & N. Ollinger (Eds.), 32-й Международный симпозиум по теоретическим аспектам информатики (STACS 2015) (Vol. 30, pp. 48-61).
источник
Если вы включите тестирование в разработку алгоритмов, Самородницкий использует аддитивную комбинаторику, чтобы показать, что линейные преобразования эффективно тестируются [здесь] .
источник
Другим примером является классическая работа Копперсмита и Винорграда 1990 года по умножению матриц, основанная на аддитивной комбинаторике.
http://www.sciencedirect.com/science/article/pii/S0747717108800132
источник