Теоретические приложения для алгоритмов аппроксимации

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

Из исследования алгоритмов аппроксимации возникла действительно прекрасная теория - связь между теоремой PCP и твердостью аппроксимации, гипотеза UGC, алгоритм аппроксимации Гомана-Уильямсона и т. Д.

Мне было интересно узнать о цели изучения алгоритмов аппроксимации для таких задач, как коммивояжёр, асимметричный коммивояжёр и другие варианты, различные проблемы в дизайне механизмов (например, на комбинаторных аукционах) и т. Д. Были ли такие аппроксимационные алгоритмы полезны в других частях теории в прошлом или они изучались исключительно ради себя?

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

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

Теперь по некоторым теоретическим причинам для изучения алгоритмов аппроксимации. Во-первых, чем объясняется тот факт, что рюкзак на практике очень прост, а раскраска графов довольно сложна? Оба NP-Hard и поли-время сводятся друг к другу. Во-вторых, изучая алгоритмы аппроксимации для особых случаев задачи, можно точно определить, какие классы примеров могут быть простыми или сложными. Например, мы знаем, что многие проблемы допускают использование PTAS в плоских и неосновных графах, тогда как в произвольных общих графах они намного сложнее. Идея аппроксимации пронизывает современный алгоритм проектирования. Например, люди используют алгоритмы потоковой передачи данных, и без объектива приближения трудно понять / разработать алгоритмы, потому что даже простые проблемы не могут быть точно решены.

$S_2^p \subseteq ZPP^{NP}$

Я также не согласен с «запиской», по крайней мере, изложенной в этой общности. В связи с этим, кто-нибудь знает, доступен ли где-нибудь разговор о премии Дэвида Джонсона Канеллакис?

Кроме того, как только мы поймем, что все NP-сложные задачи эквивалентны в отношении сложности точных решений в худшем случае, очень естественно спросить о сложности поиска приближенных решений. И Чандра замечательно говорит об изменении перспективы, которое алгоритмы аппроксимации привносят в разработку алгоритмов.

$O(\log n)$

Лучшая эвристика - это действительно приближенные алгоритмы. Самые красивые алгоритмы аппроксимации - это просто «глупая» эвристика, которая работает. Например, локальный поиск кластеризации, жадная кластеризация (Gonzalez), один по цене двух, различные жадные алгоритмы и т. Д., И т. Д., И т. Д.

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

• Переместите идеи, которые работают от эвристики, в инструменты разработки алгоритмов. Точно так же перенесите идеи из разработки алгоритмов в эвристику / алгоритмы, которые хорошо работают на практике.
• перекрестное оплодотворение между человеком, который только что закончил и должность.

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

В реальном мире очень мало точных алгоритмов - вам нужно использовать приближение, чтобы иметь удаленное отношение ...

Работа с проблемами с непрерывными переменными очень раздражает с точными алгоритмами. Например, что означает указание веса ребер экземпляра TSP с точными действительными числами?

Когда мы разрешаем алгоритмы FPTAS для этих задач, мы можем квантовать эти параметры в целые числа. Это делает проблему намного лучше (можно использовать стандартные машины Тьюринга), но имеет небольшую ошибку.