Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа - Михайлюк, В.А. (Компьютерная математика, 2012)
Для реоптимизации задачи о минимальном вершинном покрытии k-равномерного гиперграфа при добавлении h вершин (h = O(log n), n – общее число вершин) и некоторого числа гиперребер приводится полиномиальный (2–1/k) – приближенный алгоритм. При выполнении уникальной игровой гипотезы (UGC) аппроксимационное отношение 2–1/k является пороговым в семействе параметрических полиномиальных реоптимизационных алгоритмов.