Реоптимізація задачі про покриття множинами : асимптотичний поріг відношення апроксимації
Loading...
Date
2012
Authors
Михайлюк, Віктор
Ляшко, Володимир
Journal Title
Journal ISSN
Volume Title
Publisher
ВПЦ НаУКМА
Abstract
При добавленні або звільненні елемента з множини для задачі про покриття множинами існує алгоритм реоптимізації, який є асимптотично оптимальним наближеним алгоритмом, при деякому відношенні апроксимації з урахуванням стандартних умов теорії складності обчислень.
Description
Under 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.
Keywords
C-наближений алгоритм, поріг відношення апроксимації, реоптимізація, РСР теорема, C-approximation algorithm, threshold of approximation ratio, reoptimization, PCP theorem
Citation
Михайлюк В. О. Реоптимізація задачі про покриття множинами : асимптотичний поріг відношення апроксимації / Михайлюк В. О., Ляшко В. І. // Наукові записки НаУКМА. - 2012. - Т. 138 : Комп'ютерні науки. - С. 95-99.