Асимптотически точный алгоритм для задачи нескольких коммивояжёров на случайных входных данных с дискретным распределением

Рассматривается задача $m$ коммивояжёров ($m$-Peripatetic Salesman Problem) на случайных входных данных c дискретным распределением. Для её решения предлагается приближённый полиномиальный алгоритм, который при определённых ограничениях на входные данные с вероятностью, стремящейся к 1 с ростом размерности задачи, даёт точное решение задачи $m$-PSP как с одинаковыми, так и с различными весовыми функциями маршрутов коммивояжёров. Ил. 1, библиогр. 27.