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

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