Известно, что показатель TSP может быть аппроксимирован в пределах и не может быть аппроксимирован лучше, чем за полиномиальное время. Известно ли что-нибудь о поиске аппроксимационных решений за экспоненциальное время (например, менее шагов только с полиномиальным пространством)? Например, в какое время и в каком пространстве мы можем найти тур, расстояние которого не более ?123 2n1,1×OPT
44
Ответы:
Я изучил проблему и нашел самые известные алгоритмы для TSP.
1. Точные алгоритмы для TSP
1.1. Генеральный ATSP
Даже для Metric TSP нет ничего лучше, чем описанные выше алгоритмы. Это сложная задача для разработки алгоритма времени для TSP с полиномиальным пространством (см. Открытую задачу 2.2.b, Woeginger )2n
1.2. Особые случаи TSP
2. Аппроксимационные алгоритмы для TSP
2.1. Генеральный ТСП
Не может быть аппроксимирована в любой вычисляемой функции за полиномиальное время, если P = NP ( Сахни, Гонсалес ).
2.2. Метрическая ТСП
2,3. Графический TSP
2,4. (1,2) -TSP
MAX-SNP hard ( Пападимитриу, Яннакакис ).
2.5. TSP в метриках с ограниченным измерением
PTAS для TSP в евклидовом пространстве фиксированной размерности ( Arora ; Митчелл ).
TSP APX-труден в -мерном евклидовом пространстве ( Тревизан ).logn
PTAS для TSP в метриках с ограниченной удвоенной размерностью ( Bartal, Gottlieb, Krauthgamer ).
2.6. ATSP с неравенством направленного треугольника
Не может быть аппроксимировано с соотношением лучше, чем если P = NP ( Karpinski, Lampis, Schmied ).7574
2,7. TSP в графах с запрещенными несовершеннолетними
Линейное время PTAS ( Klein ) для TSP в планарных графиках.
PTAS для неосновных графиков ( Демейн, Хаджиагайи, Каварабаяси ).
2,8. MAX-TSP
2.9. Экспоненциально-временные аппроксимации
Можно вычислить -приближение для MIN-Metric-TSP за время с показательным пространством для любого или во времени с полиномиальным пространством для любого ( Боря, Буржуа, Эскофье, Пачос ).(1+ϵ) 2(1−ϵ/2)n ϵ≤25 4(1−ϵ/2)nnlogn ϵ≤23
Буду благодарен за любые дополнения и предложения.
источник
Николас Боря, Николя Бужуа, Бруно Эскофье, Вангелис Тх. Пачос: Схемы экспоненциальной аппроксимации для некоторых задач графа. Доступно онлайн .
источник
источник
Лучший tsp для взвешенных графов с ограниченным родом - http://erikdemaine.org/papers/ContractionTSP_Combinatorica/ .
источник