Аппроксимационные алгоритмы для Метрики ТСП

44

Известно, что показатель TSP может быть аппроксимирован в пределах и не может быть аппроксимирован лучше, чем за полиномиальное время. Известно ли что-нибудь о поиске аппроксимационных решений за экспоненциальное время (например, менее шагов только с полиномиальным пространством)? Например, в какое время и в каком пространстве мы можем найти тур, расстояние которого не более ?1231.5 2n1,1×OPT1231222n1.1×OPT

Алекс Головнев
источник
3
Естественный подход к решению вопросов такого типа заключается в рассмотрении иерархий линейного программирования, таких как Sherali-Adams, Lovász-Schrijver или Lasserre, которые позволяют время выполнения на м уровне (и, как правило, все более и более приближенном приближении). как растет). Однако я не знаю каких-либо положительных или отрицательных результатов о применимости иерархий к релаксации LP метрического TSP (известного как Held-Karp). г гpoly(nr)rr
MCH
3
Вы, вероятно, имеете в виду «возможно», а не «нужно»? Кроме того, я не уверен, что вы имеете в виду, находя решения в экспоненциальном времени, так как я всегда могу найти точный ответ. Я предполагаю, что вы имеете в виду «найти лучшие точки на кривой компромисса аппроксимации / сложности»?
Суреш Венкат
@ МЧ, большое спасибо, но я не нашел никаких результатов.
Алексей Головнев
@ Суреш Венкат, спасибо! Вы абсолютно правы, я имею в виду «возможно» и «лучше ...». Я исправил свой вопрос.
Алексей Головнев
Что касается Metric TSP с указанными начальной и конечной точкой, лучшим является konwn . Документ STOC 2012 «Улучшение алгоритма Christofides для TSP st Path» по адресу arxiv.org/abs/1110.4604 . 1+52
Пэн Чжан

Ответы:

53

Я изучил проблему и нашел самые известные алгоритмы для TSP.

n - количество вершин, - максимальный вес ребра. Все оценки даны с полиномиальным множителем входного размера ( ). Мы обозначим Асимметричный TSP через ATSP.Mpoly(n,logM)

1. Точные алгоритмы для TSP

1.1. Генеральный ATSP

M2nΩ(n/log(Mn)) время и пространство ( Björklund ).exp

2n времени и пространства ( Беллман ; Хельд, Карп ).2n

4nnlogn время и пространство ( Гуревич, Шелах ; Бьёрклунд, Хусфельдт ).poly

22ntnlog(nt) времени и пространства для ( Койвисто, Парвиайнен ).2tt=n,n/2,n/4,

O(Tn) время и пространство для любого с ( Койвисто, Парвиайнен ).O(Sn)2<S<2TS<4

2n×M времени и поли-пространства ( Локштанов, Недерлоф ).

2n×M времени и пространства ( Кон, Готтлиб, Кон ; Карп ; Бакс, Франклин ).M

Даже для Metric TSP нет ничего лучше, чем описанные выше алгоритмы. Это сложная задача для разработки алгоритма времени для TSP с полиномиальным пространством (см. Открытую задачу 2.2.b, Woeginger )2n

1.2. Особые случаи TSP

1.657n×M время и экспоненциально малая вероятность ошибки ( Björklund ) для неориентированного TSP.

(2ϵ)n и экспоненциальное пространство для TSP в графах с ограниченной средней степенью, зависит только от степени графа ( Cygan, Pilipczuk ; Björklund, Kaski, Koutis ).ϵ

(2ϵ)n и пространство для TSP в графах с ограниченной максимальной степенью и ограниченными целочисленными весами, зависит только от степени графа ( Björklund, Husfeldt, Kaski, Koivisto ).polyϵ

1.251n и пространство для TSP в кубических графах ( Ивама, Накашима ).poly

1.890n и пространство для TSP в графах степени ( Эппштайн ).poly4

1.733n и показательное пространство для TSP в графах степени ( Гебауэр ).4

1.657n времени и пространства для неориентированного гамильтомианского цикла ( Björklund ).poly

(2ϵ)n и экспоненциальное пространство для TSP в графах с не более гамильтоновых циклов (для любой константы ) ( Björklund, Kaski, Koutis ).dnd

2. Аппроксимационные алгоритмы для TSP

2.1. Генеральный ТСП

Не может быть аппроксимирована в любой вычисляемой функции за полиномиальное время, если P = NP ( Сахни, Гонсалес ).

2.2. Метрическая ТСП

32

123122

2,3. Графический TSP

75 ( Себо, Выген ).

2,4. (1,2) -TSP

MAX-SNP hard ( Пападимитриу, Яннакакис ).

87 -приближением ( Берман, Карпинский ).

2.5. TSP в метриках с ограниченным измерением

PTAS для TSP в евклидовом пространстве фиксированной размерности ( Arora ; Митчелл ).

TSP APX-труден в -мерном евклидовом пространстве ( Тревизан ).logn

PTAS для TSP в метриках с ограниченной удвоенной размерностью ( Bartal, Gottlieb, Krauthgamer ).

2.6. ATSP с неравенством направленного треугольника

O(1) -приближение ( Свенссон, Тарнавский, Вег )

Не может быть аппроксимировано с соотношением лучше, чем если P = NP ( Karpinski, Lampis, Schmied ).7574

2,7. TSP в графах с запрещенными несовершеннолетними

Линейное время PTAS ( Klein ) для TSP в планарных графиках.

PTAS для неосновных графиков ( Демейн, Хаджиагайи, Каварабаяси ).

2212 -аппроксимация для ATSP в плоских графах ( Гаран, Сабери ).

O(loggloglogg) -аппроксимация для ATSP в genus- графов ( Erickson, Сидиропулос ).g

2,8. MAX-TSP

79 для MAX-TSP ( Палуч, Муха, Мадри ).

78 - для MAX-Metric-TSP ( Kowalik, Mucha ).

34 для MAX-ATSP ( Paluch ).

3544 для MAX-Metric-ATSP ( Kowalik, Mucha ).

2.9. Экспоненциально-временные аппроксимации

Можно вычислить -приближение для MIN-Metric-TSP за время с показательным пространством для любого или во времени с полиномиальным пространством для любого ( Боря, Буржуа, Эскофье, Пачос ).(1+ϵ)2(1ϵ/2)nϵ254(1ϵ/2)nnlognϵ23

Буду благодарен за любые дополнения и предложения.

Алексей Головнев
источник
5
Это большое резюме того, что известно. Я бы посоветовал вам принять этот ответ (даже если он ваш).
Суреш Венкат
1
Незначительная мелочь: вы, кажется, поменялись местами для констант неприемлемости для Metric TSP и ATSP.
Майкл Лэмпис
2
Вы можете добавить планарный / ограниченный род / исключенные второстепенные графы; результаты, о которых я знаю, следующие. (1) TSP в плоских графах - линейное время PTAS ( cs.brown.edu/people/klein/publications/no-contraction.pdf ), (2) TSP в ограниченном роде / исключенные второстепенные графы - QPTAS для невзвешенных графов с исключенными минорами / взвешенные графы с ограниченным родом ( cs.emory.edu/~mic/papers/15.pdf ), (3) ATSP в плоских графах - приближение с постоянным множителем ( stanford.edu/~saberi/atsp2.pdf ).
зотачидил
4
@ Алекс Головнев: Алгоритм Бьёрклунда не работает для ATSP, он решающим образом зависит от симметрии графа.
Андреас Бьёрклунд,
3
Результат Эриксона-Сидиропулоса для ATSP - это не ясно в списке выше. PTAS Arora работает для любого фиксированного размера. Мне не нравится термин «Метрический АЦП».
Чандра Чекури
27

O(1.932n)O(2n)n(1+ϵ)O(2(1ϵ/2)n)ϵ2/5

Николас Боря, Николя Бужуа, Бруно Эскофье, Вангелис Тх. Пачос: Схемы экспоненциальной аппроксимации для некоторых задач графа. Доступно онлайн .

Винченцо
источник
10

αβα<βγα,β]γθγ2nO(θ)γ(по крайней мере, в диапазоне постоянных факторов) можно увидеть улучшения в отношении аппроксимации даже при заданном субэкспоненциальном времени. Существует несколько проблем, при которых наилучший известный результат твердости достигается за счет неэффективного снижения SAT, то есть результат твердости находится в более слабом предположении, например, NP не содержится в квазиполиномиальном времени. В таких случаях можно получить лучшее приближение за субэкспоненциальное время. Единственная, о которой я знаю, это проблема группового дерева Штейнера. Недавний известный результат - результат работы Arora-Barak-Steurer по алгоритму с субэкспоненциальным временем для уникальных игр: из этого результата мы делаем вывод, что если UGC верен, то сокращение от SAT до UGC должно быть неэффективный, то есть размер экземпляра UGC, полученного из формулы SAT, должен определенным образом увеличиваться с параметрами.

Чандра Чекури
источник
2n
1

Лучший tsp для взвешенных графов с ограниченным родом - http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .

гость
источник
спасибо, но не является ли это частным случаем результата Демейна-Гаджиагайи-Каварабаяши, на который указал Кристиан Соммер?
Алексей Головнев