Аннотация. Для произвольного ε>0 при добавлении или удалении элемента из множества задача о максимальном k-покрытие не может быть реоптимизована с отношением 1 – (1/(e + 1)) + ε, если NP ⊄ TIME(^{O(log log m)}). Приведен алгоритм реоптимизации, на котором достигается отношение аппроксимации 1 – (1/(e + 1)) + ε. Библиогр.: 14 назв.

Ключевые слова: реоптимизация, r-приближенный алгоритм.