Слегка улучшенный алгоритм аппроксимации для метрики TSP

A (Slightly) Improved Approximation Algorithm for Metric TSP

https://arxiv.org/pdf/2007.01409.pdf

С 1976 года известен «приближенный» полиномиальный алгоритм решения задачи коммивояжера: он находит решение, которое хуже оптимального не более чем на 50%. В данной статье доказывается, что некоторый (ранее известный) полиномиальный алгоритм находит решение, которое хуже оптимального не более чем на 49.9999999999999999999999999999999999%

Одной из наиболее фундаментальных проблем комбинаторной оптимизации является задача коммивояжера (TSP), формализованная еще в 1832 г. [App+07, Ch 1]). В Примере TSP нам дается набор из n городов V вместе с их попарно симметричными расстояниями, c : V xВ->Р>=0. цель состоит в том, чтобы найти Гамильтонов цикл минимальной стоимости. В метро
в задаче TSP, которую мы здесь изучаем, расстояния удовлетворяют неравенству треугольника. Поэтому задача эквивалентна нахождению замкнутого Эйлерова Связного блуждания минимальной стоимости. Она является NP-трудной, чтобы приблизить ТСП в 123 122[KLS15]. Алгоритм Христофидеса-Сердюкова [Chr76;Ser78] из четырех десятилетий назад дает 3 2-аппроксимация для TSP (см. [BS20] для исторической заметки о TSP). Это остается наиболее известным алгоритмом аппроксимации для общего случая задачи, несмотря на значительную работу, например, [Wol80;SW90;BP91;Goe95;ЦВ00;GLS05;БЕМ10;BC11;SWZ12;HNR17;HN19;KKO20].

В отличие от этого, в ряде частных случаев ТСП этот алгоритм был существенно усовершенствован. Например, были найдены полиномиально-временные аппроксимации schemes (PTAS) для евклидовых систем. [Аро96;Mit99], планарный [GKP95;Аро+98;Kle05], и метрика низкого рода [DHM07] экземпляры. Кроме того, значительное внимание было уделено случаю графических метрик. В 2011 году третий автор, Сабери и Сингх [OSS11] нашел а 32-?0 аппроксимация для этого случая. Мемке и Свенсон [Бюллетень ms11] затем получен комбинаторный алгоритм для графического ТСП с коэффициентом аппроксимации 1,461. Это соотношение позже было улучшено мухой [Muc12] к 139?1.444, а затем себе и Выгеном [SV12] до 1.4. В данной работе мы докажем следующую теорему:

Теорема 1.1.

Для некоторой абсолютной константы ?>10-36, существует рандомизированный алгоритм, который выводит тур с ожидаемой стоимостью не более 32-? умножает стоимость оптимального решения.

Отметим, что хотя алгоритм использует отношение Хельда-карпа, мы не доказываем, что разрыв интегральности этого многогранника ограничен от 3/2 Мы также замечаем, что хотя наш коэффициент аппроксимации лишь немного лучше, чем у Кристофида Эс-Сердюкова, нам не известен ни один пример, когда коэффициент аппроксимации алгоритма, который мы анализируем, превышает 4/3 в математическом ожидании.

После нового захватывающего результата Трауба, Выгена, Зенклюзена [ТВЗ20] мы также получаем следующую теорему.

Теорема 1.2.

Для некоторой абсолютной константы ?>0 существует рандомизированный алгоритм который выводит путь TSP с ожидаемой стоимостью не более 32-?умножает стоимость оптимального решения.

Источник: arxiv.org

Комментарии: