Алгоритмы решения минимаксной задачи коммивояжера. II. Двойственный подход

Предлагаются новые “резкие” нижние границы для минимаксной задачи коммивояжера в рамках линейного задания разрешающей функции. Эти границы вычисляются с полиномиальными оценками $\sim O(n^4)$ числа операций, где $n$ – размерность задачи. На основе этих границ предлагается метод ветвей и границ точного решения этой задачи.