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

21

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

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

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

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

Anon1234
источник
4
Я не уверен, что понимаю вопрос. Каковы «теоретические причины» для изучения какого-либо теоретического предмета?
Джефф
1
Я думаю, что он имеет в виду "заполнить и т. Д." в пункте 2
Гек Беннетт
2
Это неправильно, если я этим занимаюсь и никогда не задавал себе вопрос? Я просто, хотя алгоритмы аппроксимации выглядел круто!
Гопи
1
Я думаю, что мотивация такая же, как мотивация для изучения сложности аппроксимации: понять точную сложность различных задач. Алгоритм Геманса-Уильямсона неразрывно связан с трудностью уникальных игр, заключающейся в достижении большего, чем коэффициент приближения GW.
Аарон Рот
1
Я не уверен, что ваш последний абзац справедлив. Алгоритмы аппроксимации интересны тем, что представляют собой рекомендуемый способ решения неразрешимых проблем, таких как TSP. Может случиться так, что многие из них непосредственно не используются на практике в оригинальной форме, но им полезно знать, что попробовать. Вы можете сказать то же самое о точных алгоритмах, многие из которых никогда не используются непосредственно на практике, есть много технических проблем, которые необходимо учитывать при использовании любого алгоритма на практике. Многие проблемы на практике не нуждаются в точных алгоритмах, и пользователи будут полностью счастливы
Kaveh

Ответы:

21

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

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

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

S2пZппNп

Маркус Блезер
источник
9

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

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

О(журналN)

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

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

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

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

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

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

Сариэль Хар-Пелед
источник
4

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

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

Дэвид Харрис
источник