Евклидова задача коммивояжера: различия между версиями

'''Теорема 2 (Тревизан [17]). Если <math>d \ge log \; n \; </math>, то существует константа <math>\epsilon > 0 \; </math>, такая, что евклидова задача коммивояжера на <math>\mathbb{R} ^d</math> является NP-полной для аппроксимации с коэффициентом <math>1 + \epsilon \; </math>.

Основная идея алгоритмов Ароры и Митчелла достаточно проста, но детали анализа оказываются очень сложными. Оба алгоритма используют один и тот же подход. Во-первых, необходимо доказать так называемую [[структурная теорема|структурную теорему]]. Она демонстрирует, что существует <math>(1 + \epsilon) \; </math>-аппроксимация с некоторыми локальными свойствами. В случае евклидовой задачи коммивояжера существует разбиение пространства при помощи кваддерева, содержащее все точки, такие, что каждая ячейка кваддерева пересекается во время пути не более чем константное число раз и только в некоторых заранее определенных местоположениях. После доказательства структурной теоремы необходимо использовать динамическое программирование для нахождения оптимального (или близкого к оптимальному) решения, которое подчиняется локальным свойствам, обозначенным в структурной теореме.

Исходные алгоритмы, представленные в первой версии [1], представленной на конференции, и в раннем варианте [13], имели время исполнения в форме <math>O(n^{1/ \epsilon})</math>, что позволяло получить math>(1 + \epsilon ) \; </math>-аппроксимацию; впоследствии оно было улучшено. В частности, рандомизированный алгоритм Ароры [1] исполняется за время O(n(log и)1/е); он может быть дерандомизирован, в силу чего время увеличится на O(n). Результат теоремы 3 также может быть распространен на более высокие измерения. Арора демонстрирует следующий результат.