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

Рассматривается частный случай задачи отыскания $m$ гамильтоновых циклов с ограничениями на число повторений рёбер ($m$-Capacitated Peripatetic Salesman Problem, $m$-$\mathrm{CPSP}$) – задачи $2$-$\mathrm{CPSP}$ на минимум и максимум с весами рёбер из целочисленного сегмента $\{1,q\}$. Пропускные способности рёбер заданы независимыми случайными величинами, принимающими значение $2(1)$ с вероятностью $p(1-p)$. Построены алгоритмы решения задач $2$-$\mathrm{CPSP_{min}}$ и $2$-$\mathrm{CPSP_{max}}$ с гарантированными оценками точности в среднем по всем возможным входам. В частности, для задач на графах с весами рёбер $1$ и $2$ алгоритмы имеют оценки точности $(19-5p)/12$ и $(25+7p)/36$ в среднем по всем возможным входам для задачи на минимум и на максимум соответственно. Ил. 17, библиогр. 20.