Приближённые алгоритмы решения задачи о двух коммивояжёрах на максимум

Рассматривается задача отыскания в полном неориентированном графе двух рёберно непересекающихся гамильтоновых циклов (маршрутов коммивояжёра) с максимальным суммарным весом. Для случая весов рёбер из отрезка $[1,q]$ представлен полиномиальный алгоритм с гарантированной оценкой точности $\frac{3q+2}{4q+1}$. В случае весов 1 и 2 и двух различных весовых функций, соответствующих двум маршрутам, предложен полиномиальный алгоритм с оценкой точности $\frac{11\rho-8}{18\rho-15}$, где $\rho$ – оценка точности некоторого алгоритма решения аналогичной задачи на минимум. Ил. 1, библиогр. 13.