Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа

Abstract

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

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

For reoptimization of the problem of minimum vertex cover on k-uniform hypergraph by adding of h vertices ( h = O(log n), n is a total number of vertices) and a number of hyper-edges, the polynomial (2 -1/ k) - approximation algorithm is presented. If the unique game conjecture (UGC) is true, then the approximation ratio 2 -1/ k is a threshold in the family of parametric polynomial reoptimization algorithms.