Асимптотический подход к решению дискретных экстремальных задач с интервальными данными

Abstract

Предложен полиномиальный двухуровневый алгоритм линейной свертки критериев для задачи покрытия интервально взвешенного графа звездами с максимизируемой целевой функцией весового вида. Проведено обоснование достаточных условий асимптотической точности предложенного алгоритма.A polynomial two-level algorithm for the linear contraction of criterions for the problem of covering an interval-weighted graph with stars is offered when the objective function tends to a maximum. The sufficient conditions for the asymptotic accuracy of the algorithm is substantiated.