Запис Детальніше

Реоптимізація задачі про покриття множинами : асимптотичний поріг відношення апроксимації

eKMAIR

Переглянути архів Інформація
 
 
Поле Співвідношення
 
Title Реоптимізація задачі про покриття множинами : асимптотичний поріг відношення апроксимації
 
Creator Михайлюк, Віктор
Ляшко, Володимир
Liashko, Volodymyr
 
Subject C-наближений алгоритм
поріг відношення апроксимації
реоптимізація
РСР теорема
C-approximation algorithm
threshold of approximation ratio
reoptimization
PCP theorem
 
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.
При добавленні або звільненні елемента з множини для задачі про покриття множинами існує алгоритм реоптимізації, який є асимптотично оптимальним наближеним алгоритмом, при деякому відношенні апроксимації з урахуванням стандартних умов теорії складності обчислень.
 
Date 2012-12-20T08:37:56Z
2012-12-20T08:37:56Z
2012
 
Type Article
 
Identifier Михайлюк В. О. Реоптимізація задачі про покриття множинами : асимптотичний поріг відношення апроксимації / Михайлюк В. О., Ляшко В. І. // Наукові записки НаУКМА. - 2012. - Т. 138 : Комп'ютерні науки. - С. 95-99.
1996-5931
http://www.ekmair.ukma.edu.ua/handle/123456789/1923
 
Language ua
 
Relation Наукові записки НаУКМА. - 2012. - Т. 138 : Комп'ютерні науки. - С. 95-99.
 
Publisher ВПЦ НаУКМА