Михайлюк, ВікторЛяшко, Володимир2012-12-202012-12-202012Михайлюк В. О. Реоптимізація задачі про покриття множинами : асимптотичний поріг відношення апроксимації / Михайлюк В. О., Ляшко В. І. // Наукові записки НаУКМА. - 2012. - Т. 138 : Комп'ютерні науки. - С. 95-99.1996-5931https://ekmair.ukma.edu.ua/handle/123456789/1923Under an element insertion or deletion from the set for the set covering problem there exists an algorithm of reoptimization that is asymptotically optimal approximation algorithm with some approximation ratio taking into account the standard conditions of complexity theory in theoretical computer science.При добавленні або звільненні елемента з множини для задачі про покриття множинами існує алгоритм реоптимізації, який є асимптотично оптимальним наближеним алгоритмом, при деякому відношенні апроксимації з урахуванням стандартних умов теорії складності обчислень.ukC-наближений алгоритмпоріг відношення апроксимаціїреоптимізаціяРСР теоремаC-approximation algorithmthreshold of approximation ratioreoptimizationPCP theoremArticle