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

• Published in: Компьютерная математика
• Date: 2012
• Main Author: Михайлюк, В.А.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Subjects: Теория и методы оптимизации
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/84700
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос.

Для реоптимизации задачи о минимальном вершинном покрытии 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.