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

  Повний текст PDF - 171.676 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"