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

• Дата: 2012
• Автор: Михайлюк, В.А.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Назва видання: Компьютерная математика
• Теми: Теория и методы оптимизации
• Онлайн доступ: http://dspace.nbuv.gov.ua/handle/123456789/84700
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос.

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