Симметричная задача коммивояжера II. Новые нижние границы

Для симметричной задачи коммивояжера предлагаются метод ветвей и границ, где в качестве границ предлагаются две нижние границы. Первая граница – решение задачи об оптимальном $2$-паросочетании, вторая – о минимальном покрытии $1$-дерева. Последняя граница усиливается за счет применения задачи об оптимальном 2-паросочетании. Обе эти границы существенно улучшают симметричную задачу коммивояжера по сравнению с асимметричной задачей.

Статья представлена к публикации членом редколлегии: А. А. Лазарев