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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2012
1. Verfasser:	Михайлюк, В.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Schriftenreihe:	Компьютерная математика
Schlagworte:	Теория и методы оптимизации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/84700
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-84700
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-847002025-02-23T18:38:50Z Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа Реоптимізація задачі про мінімальне вершинне покриття k-рівномірного гіперграфа Reoptimization of minimum vertex cover problem on k-uniform hypergraph Михайлюк, В.А. Теория и методы оптимизации Для реоптимизации задачи о минимальном вершинном покрытии 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. 2012 Article Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84700 519.854 ru Компьютерная математика application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Теория и методы оптимизации Теория и методы оптимизации
spellingShingle	Теория и методы оптимизации Теория и методы оптимизации Михайлюк, В.А. Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа Компьютерная математика
description	Для реоптимизации задачи о минимальном вершинном покрытии k-равномерного гиперграфа при добавлении h вершин (h = O(log n), n – общее число вершин) и некоторого числа гиперребер приводится полиномиальный (2–1/k) – приближенный алгоритм. При выполнении уникальной игровой гипотезы (UGC) аппроксимационное отношение 2–1/k является пороговым в семействе параметрических полиномиальных реоптимизационных алгоритмов.
format	Article
author	Михайлюк, В.А.
author_facet	Михайлюк, В.А.
author_sort	Михайлюк, В.А.
title	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
title_short	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
title_full	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
title_fullStr	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
title_full_unstemmed	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
title_sort	реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2012
topic_facet	Теория и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/84700
citation_txt	Реоптимизация задачи о минимальном вершинном покрытии k-равномерного гиперграфа / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 1. — С. 158-166. — Бібліогр.: 9 назв. — рос.
series	Компьютерная математика
work_keys_str_mv	AT mihajlûkva reoptimizaciâzadačiominimalʹnomveršinnompokrytiikravnomernogogipergrafa AT mihajlûkva reoptimízacíâzadačípromínímalʹneveršinnepokrittâkrívnomírnogogípergrafa AT mihajlûkva reoptimizationofminimumvertexcoverproblemonkuniformhypergraph
first_indexed	2025-11-24T11:42:22Z
last_indexed	2025-11-24T11:42:22Z
_version_	1849671855204466688
fulltext	158 Компьютерная математика. 2012, № 1 Для реоптимизации задачи о ми- нимальном вершинном покрытии k-равномерного гиперграфа при добавлении h вершин (h = O(log n), n – общее число вершин) и неко- торого числа гиперребер приво- дится полиномиальный (2–1/k) – приближенный алгоритм. При выполнении уникальной игровой гипотезы (UGC) аппроксимаци- онное отношение 2–1/k является пороговым в семействе парамет- рических полиномиальных реоп- тимизационных алгоритмов.  В.А. Михайлюк, 2012 УДК 519.854 В.А. МИХАЙЛЮК РЕОПТИМИЗАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЕРШИННОМ ПОКРЫТИИ K-РАВНОМЕРНОГО ГИПЕРГРАФА Введение. Задача о минимальном вершин- ном покрытии – проблема нахождения наи- меньшего множества вершин, которые каса- ются всех ребер в данном графе. Это одна из основных NP -полных проблем и поэтому решить ее точно за приемлемое время вряд ли представляется возможным. Поэтому рас- сматриваются эффективные (полиномиаль- ные) приближенные алгоритмы для решения таких задач. Для минимизационной (максими- зационной) проблемы говорят, что алгоритм есть C – приближенный алгоритм, если он для произвольного экземпляра дает решение со значением целевой функции не большим, чем C OPT (не меньшим, чем 1 OPT C ⋅ ), где OPT – глобальный оптимум. При этом C называют отношением аппроксимации. Говорят, что для проблемы Q установлена верхняя оценка отношения аппроксимации C, если существует полиномиальный C – приближенный алгоритм для решения Q . Для проблемы Q установлена нижняя оцен- ка отношения аппроксимации c , если для произвольного 0ε > не существует полино- миального приближенного алгоритма для Q , на котором достигается отношение аппрок- симации c − ε (или строго меньше c). Если C = c, то для проблемы Q установлен порог отношения аппроксимации (равный C c= ). Соответствующий алгоритм называется по- Компьютерная математика. 2012, № 1 159 роговым или оптимальным (и отношение аппроксимации – оптимально). В.А. МИХАЙЛЮК 160 Компьютерная математика. 2012, № 1 Для задачи о минимальном вершинном покрытии известен простой 2-приближенный алгоритм, основанный на применении паросочетаний. Несмот- ря на многочисленные попытки существенно улучшить эту оценку удалось дос- тичь лишь аппроксимационного отношения 2 (1)o− [1, 2]. Проблема установления нижних оценок отношения аппроксимации (как и любая проблема получения нижних оценок сложности) является очень трудной задачей. Для такой проблемы существует название неаппроксимируемость (inapproximability) или трудность аппроксимации (hardness of approximation). Большое влияние на развитие методов получения нижних оценок оказала знаме- нитая PCP теорема [3]. Используя эти достижения Хастад (Hastad) [4] получил нижнюю оценку 7 6 для задачи о минимальном вершинном покрытии. Динур (Dinur) и Сафра (Safra) улучшили эту оценку до 1.36 [5]. Совсем недавно Кхот (Khot) [6] получил оценку 2 − ε , используя в своих построениях так называемую уникальную игровую гипотезу (Unique Games Con- jecture, UGC). С помощью UGC удалось установить ряд других пороговых ре- зультатов в аппроксимации. Понятие реоптимизации [7–9] состоит в следующем. Пусть Q − некоторая NP -трудная (возможно, NP -полная) проблема, I − начальный экземпляр про- блемы Q , оптимальное решение которого известно. Предлагается новый экзем- пляр 'I задачи Q , полученный некоторыми «незначительными» изменениями экземпляра I . Как можно эффективно использовать знания об оптимальном ре- шении I для вычисления точного или приближенного решения экземпляра ' ?I Мало изученной и исследованной есть проблема нахождения пороговых (оптимальных) приближенных алгоритмов для реоптимизации дискретных задач оптимизации. Данная работа посвящена изучению этого вопроса для задачи о минимальном вершинном покрытии графа. Постановка задачи. Рассмотрим общую задачу вершинного покрытия k-равномерного гиперграфа. Определение 1. k-равномерный гиперграф ( , )H V E= состоит из множества вершин V и множества E k-элементных подмножеств V , называемых гипер- ребрами (или просто ребрами). Вершинное покрытие H состоит из подмножест- ва вершин S V⊆ такого, что каждое гиперребро из E пересекается с S, т. е. e S∩ ≠ ο для любого e E∈ . Независимое множество в H есть подмноже- ство, дополнение которого есть вершинное покрытие, или, иными словами, под- множество вершин, которое полностью не содержит в себе никакого гиперребра. Проблема Ek Vertex Cover− − – проблема нахождения вершинного покрытия минимального размера в k-равномерном гиперграфе. Заметим, что при 2k = это обычная задача о минимальном вершинном по- крытии графа. РЕОПТИМИЗАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЕРШИННОМ ПОКРЫТИИ … Компьютерная математика. 2012, № 1 161 Определение 2. Гиперребро e E∈ инцидентно вершине v V∈ , если v e∈ . Паросочетание – подмножество гиперребер графа, такое, что никакие два гиперребра из этого подмножества не инцидентны какой-либо одной вершине. Теорема 1. Существует полиномиальный k -приближенный алгоритм для задачи .Ek Vertex Cover− − Доказательство основано на построении множества паросочетаний гипер- графа, вершины которого составляют приближенное покрытие. В качестве реоптимизационной версии задачи о минимальном вершинном покрытии k-равномерного гиперграфа рассмотрим задачу с добавлением неко- торого числа h вершин с некоторыми инцидентными им гиперребрами. Более точно. Проблема. Insh Ek Vertex Cover− − − . Входные данные. Экземпляр I про- блемы Ek Vertex Cover− − (граф ( , )H V E= ) и его оптимальное решение min IV V⊆ . Результат. Найти оптимальное решение экземпляра 'I проблемы Ek Vertex Cover− − (граф ( ', ')H V E= , где ' { }, 1,...,iV V v i h= ∪ = ; ' { },jE E e= ∪ 1,...,j l= , вместе с вершинами iv добавляются некоторые инцидентные им гиперребра je ), используя при этом min IV . Цель. Минимизировать число вершин в 'I . Проблема Insh Ek Vertex Cover− − − является реоптимизацией Ek Vertex− − Cover− при добавлении h вершин. Нижние оценки отношения аппроксимации и уникальная игровая ги- потеза (UGC). Полезен и интересен вопрос об установлении NP -трудности ре- оптимизационных вариантов задач оптимизации. Можно показать, что проблема Insh Ek Vertex Cover− − − является NP -трудной даже для 1h = . Будем пользоваться результатами работы [6]. Типичную технику получения результатов по нижним оценкам отношения аппроксимации (неаппроксимируе- мости) можно описать следующим образом. Источником является следующее рассуждение. Пусть P − произвольная оптимизационная (для определенности на максимум) проблема. Под ( . )c s gap− версией проблемы P (обозначение ,c sGap P− ) будем понимать проблему, для которой либо ( )OPT I c≥ , либо ( )OPT I s≤ для произвольного экземпляра I P∈ . Рассмотрим NP -полную про- блему 3-Sat (3-выполнимость). Произвольная 3-Sat формула ( 3E CNF− фор- мула) – это конъюнкция множества скобок, где каждая скобка является дизъ- юнкцией трех булевских переменных или их отрицанием. Цель состоит в опре- делении приписывания булевским переменным таких значений истинности, что формула становится логически истинной (выполнимой). Допустим, что сущест- вует полиномиальная сводимость от 3-Sat к ,c sGap P− для некоторых 0 ,s c< < т. е. сводимость, которая отображает 3-Sat формулу ψ на экземпляр I проблемы P такой, что: В.А. МИХАЙЛЮК 162 Компьютерная математика. 2012, № 1 случай-да: если ψ имеет приписывание, которое делает ее выполнимой, то ( )OPT I c≥ ; случай-нет: если ψ не имеет приписываний, которые делают ее выполни- мой, то ( )OPT I s≤ . Такая сводимость предполагает, что если существует полиномиальный ал- горитм с отношением аппроксимации строго меньшим, чем c s для проблемы P , т. е. возможность эффективно определить выполнима ли 3-Sat формула и, сле- довательно, P NP= . Таким образом, при стандартном предположении P NP≠ эта сводимость – источник получения результатов по неаппроксимируемости для проблемы P . Будем исходить из PCP (Prababilistically Checkable Proof) тео- ремы [3] в той или иной форме для некоторого NP-полного языка (например 3- Sat). Конструируется PCP система или вероятностно проверяемая система дока- зательств (Probabilistically Checkable Proof system, PCPs) для данной проблемы P , которая осуществляет сводимость к проблеме (языку), неаппроксимируе- мость которой нужно установить (например, ,c sGap P− ). Экземпляр (взвешенной) проблемы о покрытии метками представляется как кортеж ( , , , , )X Y R WΦ = Ψ . Множества X и Y представляют переменные: будем обращаться к переменным в X как к левым переменным, а к переменным в Y − как к правым вершинам. Множество R− множество возможных меток. Для лю- бых , ,x X y Y∈ ∈ Ψ содержит одно отношение xy R Rψ ⊆ × и W содержит веса 0xyw ≥ . Маркировка (расстановка меток) – функция :L X Y R∪ → . Будем гово- рить, что ограничение xyψ удовлетворяет маркировке L , если ( ( ), ( )) xyL x L y ∈ψ . Определим ( , ) xy y Y w x w ∈ Φ =∑ и , ( ) xy x X y Y w w ∈ ∈ Φ = ∑ , аналогично определяются ( , ), ( )L Lw x wΦ Φ только суммы берутся по всем y и по всем ,x yтаким, что xyψ удовлетворяет L . PCP теорема [3, 6] показывает, что проблема о покрытии мет- ками является в определенном смысле NP -трудной. С помощью зтой теоремы были установлены многие нижние оценки отно- шения аппроксимации [4], однако применить ее для доказательства неаппрокси- мированости 2− ε задачи о минимальном вершинном покрытии не удавалось. Учитывая это Кхот ввел UGC [6]. В частности ограничения в Ψ имеют специальную форму: будем говорить, что xyψ ∈ Ψ является уникальным, если для любого a R∈ существует уникаль- ный b R∈ , такой что ( , ) xya b ∈ψ и наоборот; иными словами, xyψ можно счи- тать как паросочетание между метками x и метками y . Будем говорить, что эк- земпляр Φ уникален, если все ограничения уникальны. РЕОПТИМИЗАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЕРШИННОМ ПОКРЫТИИ … Компьютерная математика. 2012, № 1 163 Гипотеза (Взвешенная Уникальная Игровая Гипотеза) [6]. Для произ- вольных , 0ς γ > существует R такой, что следующее является NP -трудным. Для данного взвешенного уникального экземпляра Φ проблемы о покрытии метками с множеством меток Rи с ( ) 1w Φ = отличить данные два случая: случай-да: существует маркировка L такая, что ( ) 1Lw Φ ≥ − ς ; случай-нет: для произвольной маркировки , ( ) γ.LL w Φ ≤ Исходя из сформулированной гипотезы в [6] выводится так называемая сильная форма уникальной игровой гипотезы после чего устанавливается сво- димость к проблеме Ek Vertex Cover− − . В случае-да гиперграф, полученный в результате сводимости содержит независимое множество веса 1 1 2 k − − ε и в слу- чае-нет гиперграф содержит независимое множество веса δ . Поскольку допол- нение независимого множества является вершинным покрытием, то отсюда сле- дует неаппроксимируемость Ek Vertex Cover− − любой константой меньшей k . Этот результат можно сформулировать в виде такой теоремы. Теорема 2 [6]. При выполнении уникальной игровой гипотезы (UGC) для произвольного 0ε > является NP -трудным аппроксимировать Ek Vertex Cover− − с отношением k − ε . Порог отношения аппроксимации реоптимизации задачи о минималь- ном вершинном покрытии. Используя подход, предложенный в [8, 9] докажем теорему. Теорема 3. Если (log )h O n= ( n − число вершин в гиперграфе), то для про- блемы Insh Ek Vertex Cover− − − (реоптимизация Ek Vertex Cover− − ) существу- ет 1 (2 ) k − – приближенный (полиномиальный) алгоритм. Доказательство. Пусть min IV − оптимальное решение экземпляра I пробле- мы Ek Vertex Cover− − и min( )Iw V − вес решения (рассматриваем в общем случае взвешенный вариант). Пусть ( 1,..., )iv i h= добавленные вершины вместе с неко- торыми гиперребрами ( 1,..., )je j l= (экземпляр 'I ) и ' min IV − оптимальное реше- ние 'I . Ясно, что min 1{ ,..., }I hV v v∪ − допустимое решение 'I . Если ' min IV содержит 1{ ,..., }hv v , то min 1{ ,..., }I hV v v∪ − оптимальное решение. Рассмотрим случай, когда ' min IV не содержит 1{ ,..., }hv v . Обозначим ( 1,...,2 1)h iW i = − все подмножества 1{ ,..., }hv v без пустого множе- ства и ( )iN W множество всех вершин гиперграфа соседних с iW (т. е. соединен- ных с вершинами из iW гиперребрами). Если ' min IV не содержит iW , то min ( )I iV N W∪ допустимое решение 'I . В этом случае построим еще одно допу- стимое решение iV : В.А. МИХАЙЛЮК 164 Компьютерная математика. 2012, № 1 - удалим все iW и ( )iN W из гиперграфа; - к оставшемуся гиперграфу применим ρ -приближенный алгоритм нахож- дения вершинного покрытия; - к полученному решению добавим ( )iN W . Среди решений min ( )I iV N W∪ и iV выберем наилучшее (т. е. с меньшим зна- чением целевой функции w), которое в дальнейшем обозначим iV . Поскольку ' min min( ) ( )I Iw V w V≤ получаем ' min min( ( )) ( ) ( ( ))I I i iw V N W w V w N W∪ ≤ + (1) и в силу построения iV ' ' min min( ) ( ( ) ( ( )) ( ( )) ( ) ( 1) ( ( ))I I i i i iw V w V w N W w N W w V w N W≤ ρ − + = ρ − ρ − . (2) Взяв линейную комбинацию (1) с коэффициентом ( 1)ρ − и (2) получаем ' ' ' min min min min( 1) ( ( )) ( ) ( 1) ( ) ( ) (2 1) ( ).I I I I i iw V N W w V w V w V w Vρ − ∪ + ≤ ρ − + ρ = ρ − Поскольку min min( 1) ( ( )) ( ) ( 1 1)min{ ( ( )), ( )} ( )I I i i i i iw V N W w V w V N W w V w Vρ − ∪ + ≥ ρ − + ∪ = ρ , имеем ' min( ) (2 1) ( )I iw V w Vρ ≤ ρ − . Таким образом, получены приближенные реше- ния iV экземпляра 'I , для которых ' ' min min 2 1 1 ( ) ( ) (2 ) ( )I I iw V w V w V ρ −≤ = − ρ ρ . Так как каждое решение ( 1,...,2 1)h iV i = − является 1 (2 )− ρ – приближенным (одно из них будет задействовано), то получен 1 (2 )− ρ – приближенный алгоритм для Insh Ek Vertex Cover− − − . Для полиномиальности данного алгоритма достаточ- но потребовать, чтобы 2h cn≤ , где const,c = отсюда следует условие (log )h O n= . Для завершения доказательства нужно положить kρ = , т. е. при- менить приближенный алгоритм из теоремы 1. Лемма 1. Если (log )h O n= ( n − число вершин в гиперграфе), выполнена уникальная игровая гипотеза (UGC) и для проблемы Insh Ek Vertex Cover− − − (реоптимизация Ek Vertex Cover− − ) существует γ – приближенный (полиноми- альный) алгоритм, то 1 2 k γ ≥ − . РЕОПТИМИЗАЦИЯ ЗАДАЧИ О МИНИМАЛЬНОМ ВЕРШИННОМ ПОКРЫТИИ … Компьютерная математика. 2012, № 1 165 Доказательство. При доказательстве теоремы 4 для проблемы Insh Ek Vertex Cover− − − разработано семейство приближенных (полиномиаль- ных) параметрических (зависящих от ρ ) алгоритмов с отношением аппроксима- ции 1 ( ) 2φ ρ = − ρ , которые для решения произвольного экземпляра 'I использу- ют оптимальное решение min IV экземпляра I (в это семейство входит любой полиномиальный γ -приближенный алгоритм с таким свойством). В нашем слу- чае ( )γ = φ ρ и нужно доказать, что 1 ( ) 2 k φ ρ ≥ − . Доказательство проведем от противного. Пусть 1 ( ) 2 ( )k k φ ρ < − = φ , поскольку функция ( )φ ρ как функция своего параметра ρ является возрастающей, то отсюда следует, что kρ < . А это, поскольку выполняется UGC, противоречит теореме 2, так как такого полиноми- ального ρ -приближенного алгоритма просто не существует. Лемма доказана. Теорема 4 . Если (log )h O n= (n − число вершин в гиперграфе) и выполнена уникальная игровая гипотеза (UGC), то для проблемы Insh Ek Vertex Cover− − − (реоптимизация Ek Vertex Cover− − ) существует оптимальный (пороговый) 1 (2 ) k − – приближенный алгоритм. Доказательство. Теорема 3 устанавливает верхнюю оценку отношения ап- проксимации для проблемы Insh Ek Vertex Cover− − − . Фактически лемма 1 устанавливает нижнюю оценку аппроксимации для этой проблемы. Поскольку верхняя оценка совпадает с нижней и равна 1 2 k − , то тем самым теорема доказана. Заключение. В работе получен следующий результат. Для задачи Insh Ek Vertex Cover− − − ( реоптимизация Ek Vertex Cover− − с добавлением h вершин с некоторыми гиперребрами) существует полиномиальный 1 (2 ) k − – приближенный алгоритм, если (log )h O n= . При выполнении уникальной игро- вой гипотезы (UGC) отношение аппроксимации 1 2 k − является пороговым в се- мействе параметрических полиномиальных реоптимизационных алгоритмов. В частности для 2k = (задача о минимальном вершинном покрытии графа) по- лучен оптимальный (пороговый) 3 2 – приближенный реоптимизационный алго- ритм при добавлении ( (log ))h h O n= вершин в граф. Справедливость полученно- го результата зависит от истинности уникальной игровой гипотезы (UGC), что является одной из основных открытых проблем современной теоретической ин- форматики. В.А. МИХАЙЛЮК 166 Компьютерная математика. 2012, № 1 В.О. Михайлюк РЕОПТИМІЗАЦІЯ ЗАДАЧІ ПРО МІНІМАЛЬНЕ ВЕРШИННЕ ПОКРИТТЯ K-РІВНОМІРНОГО ГІПЕРГРАФА Для реоптимізації задачі про мінімальне покриття k -рівномірного гіперграфа при добавленні h вершин ( (log ),h O n n= − загальна кількість вершин) і деякого числа гіперребер наводиться поліноміальний (2 1/ )k− -наближений алгоритм. При виконанні унікальної ігрової гіпотези (UGC) апроксимаційне відношення 2 1/k− є пороговим в сімействі параметричних поліноміальних реоптимізаційних алгоритмів. V.A. Mikhailyuk REOPTIMIZATION OF MINIMUM VERTEX COVER PROBLEM ON K-UNIFORM HYPERGRAPH For reoptimization of the problem of minimum vertex cover on k-uniform hypergraph by adding of h vertices ( (log ),h O 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 ratio2 1/k− is a threshold in the family of parametric polynomial reoptimization algorithms. 1. Halperin E. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs // SIAM J. on Computing. – 2002. – 31(5). – P. 1608 – 1623. 2. Karakostas G. A better approximation ratio for the vertex cover problem // In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP). – 2005. – Lisbon, Portugal. – P. 1043 – 1050. 3. Arora S., Lund C., Motwani R., Sudan M. and Szegedy M. Proof verification and intractability of approximation problems // J. of the ACM. – 1998. – 45, N 3. – P. 501 – 555. 4. Hastad J. Some optimal inapproximability results // J. of the ACM. – 2001. – 48, N 4. – P. 798 – 859. 5. Dinur I. and Safra S. On the hardness of approximating minimum vertex cover// Annals of Mathematics. – 2005. – 162(1). – P. 439 – 485. 6. Khot S., Regev O. Vertex cover might be hard to approximate to within 2 − ε // J. Comput. Syst. Sci. – 2008. – 74(3). – P. 335 – 349. 7. Bockenhauer H.J., Hromkovic J., Momke T. and Widmayer P. On the hardness of reoptimiza- tion // Lect. Notes Comput. Sci. – 2008. – Springer: Berlin. – 4910. – P. 50–65. 8. Ausiello G., Bonifaci V. and Escoffier B. Complexity and approximation in reoptimization // Computability in Context: Computation and Logic in the Real World (ed. S. Barry Cooper and Andrea Sorbi). – 2011. – London: Imperial College Press. – P. 101 – 130. 9. Михайлюк В.А. Реоптимизация задачи о покрытии множествами // Кибернетика и сис- темный анализ. – 2010. – 46, № 6. – С. 27–31. Получено 21.10.2011 Об авторе: Михайлюк Виктор Алексеевич, кандидат физико-математических наук, доцент, докторант Института кибернетики имени В.М. Глушкова НАН Украины. e-mail: mikhailyukvictor2@gmail.com

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

Institution

Ähnliche Einträge