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

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