Том 3, номер 1, 1996 г., Стр. 75-79
УДК 519.854
А. И. Сердюков
Об одном свойстве задачи коммивояжера на максимум в двумерном нормированном пространстве
Аннотация:
Показано, что для любого множества$X_n=\{x_1,\dots, x_n\}$ точек на плоскости с метрикой Минковского$\mu$ найдется циклическая подстановка$s_0=s_0(X_n)$ из симметрической группы подстановок$S_n$ такая, что
$$ \sum^n_{i=1}µ(x_i,x_{s_0(i)})\geq\max\sum^n_{i=1}µ(x_i,x_{s(i)}) $$
где$s$ произвольная подстановка из$S_n$ , состоящая из нечетных циклов.
Библиогр. 5.
Сердюков А. И. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 22 декабря 1995 г.
