Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
|
|
| Creator |
Михайлюк, В.А.
|
|
| Subject |
Теория и методы оптимизации
|
|
| Description |
Для реоптимизации задачи о минимальном вершинном покрытии 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. |
|
| Date |
2015-07-12T18:13:31Z
2015-07-12T18:13:31Z 2012 |
|
| Type |
Article
|
|
| Identifier |
Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос.
ХХХХ-0003 http://dspace.nbuv.gov.ua/handle/123456789/84700 519.854 |
|
| Language |
ru
|
|
| Relation |
Компьютерная математика
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|