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

Цикловым покрытием графа называется остовный подграф, компоненты связности которого являются простыми циклами. Рассматривается труднорешаемая задача отыскания в полном взвешенном ориентированном графе циклового покрытия максимального веса, которое удовлетворяет верхнему ограничению на количество входящих в него циклов и нижнему ограничению на количество дуг в каждом цикле. Предложен полиномиальный алгоритм решения этой задачи в геометрическом случае, когда вершины заданного графа являются точками в многомерном вещественном пространстве, а расстояния между ними индуцированы положительно однородной функцией, единичный шар которой является произвольным выпуклым политопом с фиксированным числом фасет. Полученный результат развивает идеи, лежащие в основе известного алгоритма для полиэдральной задачи коммивояжера на максимум.