кафедра математических основ управления аспирант, ассистент, 141700, Московская облаcть, г. Долгопрудный, Институтский пер., 9
кафедра математических основ управления аспирант, ассистент, Institutskiy pereulok, 9, Dolgoprudny, Moscow region, 141700, Russia
Задача комбинаторной оптимизации называется устойчивой, если ее решение сохраняется при возмущении входных параметров, не превышающих некоторого порогового значения – радиуса устойчивости. В работах [1–3], в предположении об устойчивости входа, построены точные полиномиальные алгоритмы для некоторых NP-трудных задач о разрезах. В настоящей работе показано, как строить ускоренные алгоритмы для достаточно устойчивых полиномиальных задач. Подход иллюстрируется на примере известной задачи о минимальном разрезе (MINCUT). Построен O(n²) точный алгоритм решения n-устойчивой задачи MINCUT. Кроме того, построен полиномиальный алгоритм вычисления радиуса устойчивости задачи MINCUT и получен простой критерий n-устойчивости.
A combinatorial optimization problem is called stable if its solution is preserved under perturbation of the input parameters that do not exceed a certain threshold – the stability radius. In [1–3] exact polynomial algorithms have been built for some NP-hard problems on cuts in the assumption of the entrance stability. In this paper we show how to accelerate some algorithms for sufficiently stable polynomial problems. The approach is illustrated by the well-known problem of the minimum cut (MINCUT). We built an O(n²) exact algorithm for solving n-stable instance of the MINCUT problem. Moreover, we present a polynomial algorithm for calculating the stability radius and a simple criterion for checking n-stability of the MINCUT problem.
The authors declare that there are no conflicts of interest present.