Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
При виконаннi унiкальної iгрової гiпотези (UGC) для розв’язання задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-EkCSP-P при додаваннi довiльного обмеження) при k = const iснує полiномiальний оптимальний (пороговий) ψ(αZ)-наближений алгоритм, де ψ(αZ) = 2 − 1/αz i αZ — цiлочисловий розрив напiввизначеної...
Збережено в:
| Дата: | 2013 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Назва видання: | Доповіді НАН України |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/85358 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-85358 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-853582015-07-29T03:01:53Z Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності Михайлюк, В.О. Інформатика та кібернетика При виконаннi унiкальної iгрової гiпотези (UGC) для розв’язання задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-EkCSP-P при додаваннi довiльного обмеження) при k = const iснує полiномiальний оптимальний (пороговий) ψ(αZ)-наближений алгоритм, де ψ(αZ) = 2 − 1/αz i αZ — цiлочисловий розрив напiввизначеної (SDP) релаксацiї Max-EkCSP-P задачi Z. При выполнении уникальной игровой гипотезы для решения задачи Ins-Max-EkCSP-P (реоптимизация Max-EkCSP-P при добавлении произвольного ограничения) при k = const существует полиномиальный оптимальный (пороговый) ψ(αZ)-приближенный алгоритм, где ψ(αZ) = 2 − 1/αZ и αZ — целочисленный разрыв полуопределенной (SDP) релаксации Max-EkCSP-P задачи Z. When the unique game conjecture is hold for the problem Ins-Max-EkCSP-P (reoptimization of Max-EkCSP-P under insertion of any constraint), an polynomial optimal (threshold) ψ(αZ)-approximation algorithm exists, where ψ(αZ) = 2 − 1/αZ, k = const, and αZ is the integrality gap of a semidefinite relaxation of the Max-EkCSP-P problem Z. 2013 Article Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/85358 519.854 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Михайлюк, В.О. Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності Доповіді НАН України |
| description |
При виконаннi унiкальної iгрової гiпотези (UGC) для розв’язання задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-EkCSP-P при додаваннi довiльного обмеження) при k = const iснує полiномiальний оптимальний (пороговий) ψ(αZ)-наближений алгоритм,
де ψ(αZ) = 2 − 1/αz i αZ — цiлочисловий розрив напiввизначеної (SDP) релаксацiї Max-EkCSP-P задачi Z. |
| format |
Article |
| author |
Михайлюк, В.О. |
| author_facet |
Михайлюк, В.О. |
| author_sort |
Михайлюк, В.О. |
| title |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_short |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_full |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_fullStr |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_full_unstemmed |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_sort |
поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2013 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/85358 |
| citation_txt |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT mihajlûkvo polínomíalʹnaporogovareoptimízacíâzadačprouzagalʹnenuvikonuvanístʹzpredikatamiobmeženoírozmírností |
| first_indexed |
2025-07-06T12:34:19Z |
| last_indexed |
2025-07-06T12:34:19Z |
| _version_ |
1836900953579585536 |
| fulltext |
УДК 519.854
В.О. Михайлюк
Полiномiальна порогова реоптимiзацiя задач
про узагальнену виконуванiсть з предикатами
обмеженої розмiрностi
(Представлено академiком НАН України I. В. Сергiєнком)
При виконаннi унiкальної iгрової гiпотези (UGC) для розв’язання задачi Ins-Max-
EkCSP-P (реоптимiзацiя Max-EkCSP-P при додаваннi довiльного обмеження) при k =
= const iснує полiномiальний оптимальний (пороговий) ψ(αZ)-наближений алгоритм,
де ψ(αZ) = 2 − 1/αZ i αZ — цiлочисловий розрив напiввизначеної (SDP) релаксацiї Max-
EkCSP-P задачi Z.
У задачах про узагальнену виконуванiсть (CSP задачах) є множина змiнних i множина
обмежень (вони задаються предикатами), кожне з яких залежить вiд деякого числа змiн-
них. Бiльш формально, CSP задача Q задається множиною предикатiв над скiнченною
областю [q] = {1, . . . , q}. Кожен екземпляр цiєї задачi складається з множини змiнних V
i множини обмежень на них. Задача полягає у знаходженнi такого приписування значень
змiнним, якi виконують (задовольняють) максимальне число обмежень. У загальному ви-
падку предикати можуть бути замiненi дiйсними платiжними функцiями, i задача полягає
в максимiзацiї загального платежу. Велика кiлькiсть оптимiзацiйних задач, таких як Max-
Cut i Max-k-Sat, є прикладами CSP задач. Бiльшiсть задач про узагальнену виконуванiсть
є NP-складними i їх точне розв’язання за допустимий час навряд чи можливе. Тому розгля-
даються ефективнi наближенi алгоритми розв’язання таких задач. Кажуть, що для задачi
максимiзацiї алгоритм є C-наближеним, якщо за допомогою нього для довiльного екзем-
пляра знаходиться розв’язок iз значенням цiльової функцiї, не меншим, нiж (1/C) · OPT ,
де OPT — глобальний оптимум. При цьому C називають вiдношенням апроксимацiї.
Вважається, що для задачi Q встановлена верхня оцiнка вiдношення апроксимацiї C,
якщо iснує полiномiальний C-наближений алгоритм її розв’язання. Для цiєї задачi вста-
новлена нижня оцiнка вiдношення апроксимацiї c, якщо для довiльного ε > 0 не iснує
полiномiального наближеного алгоритму її розв’язання, на якому досягається вiдношення
апроксимацiї c−ε. Якщо C = c, то для задачi Q встановлено порiг вiдношення апроксимацiї
C = c. Вiдповiдний алгоритм називається оптимальним, або пороговим.
Задача встановлення нижнiх оцiнок вiдношення апроксимацiї (як i довiльна задача отри-
мання нижнiх оцiнок складностi) є дуже важкою. Для неї iснує назва неапроксимованiсть
або складнiсть апроксимацiї. Значний вплив на розвиток методiв одержання нижнiх оцi-
нок мали вiдома PCP теорема [1] i дискретний аналiз Фур’є для тестування властивостей
задач [2].
Починаючи з роботи [3], що стосується задачi Max-Cut, напiввизначене програмування
(SDP) стало основним iнструментом у побудовi наближених алгоритмiв для CSP задач. Для
багатьох задач побудованi SDP релаксацiї i застосовуються вiдповiднi процедури ймовiр-
нiсного округлення отриманих розв’язкiв.
© В. О. Михайлюк, 2013
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №1 37
Проблема неапроксимованостi була успiшно розв’язана для багатьох задач завдяки PCP
теоремi. Зокрема, Хастад [5] показав, що Max-E3-Lin-2 i Max-3-Sat є NP-складними для
апроксимацiї з вiдношеннями 2−ε i 8/7−ε вiдповiдно. Це означає, що найпростiший випад-
ковий алгоритм приписування є найкращим (оптимальним) для цих задач, якщо P 6= NP ,
або що вiдношення 2 i 8/7 є пороговими. Таким чином, iнодi випадковий алгоритм припи-
сування є оптимальним. Задачi (зокрема i предикати), для яких це має мiсце, називають
апроксимацiйно-стiйкими.
Останнiм часом встановлено тiсний зв’язок мiж поняттями апроксимацiйне вiдношен-
ня, вiдношення неапроксимованостi та цiлочисловий розрив простої SDP релаксацiї (що
визначається як максимальне вiдношення значення SDP розв’язку до значення оптимуму).
Унiкальна iгрова гiпотеза (UGC) була введена Кхотом [7] як можливий спосiб одержання
нових сильних результатiв з неапроксимованостi. Її можна сформулювати в термiнах унi-
кальної iгрової задачi, UGC є посиленням PCP теореми. Якщо виходити з UGC, отримаємо
неапроксимованiсть, основану на UGC, або умовну неапроксимованiсть.
З iстинностi UGC випливає, що проста SDP релаксацiя дає оптимальне вiдношення
апроксимацiї для CSP задачi. Вперше зв’язок мiж схемами округлення для SDP релаксацiї
i результатами з неапроксимованостi, що випливають з UGC, було встановлено в [9] для
булевих CSP задач вiд двох змiнних.
Поняття реоптимiзацiї [10, 11] полягає в наступному. Нехай Q — деяка NP -складна
(можливо NP -повна) задача, I — її початковий екземпляр, оптимальний розв’язок якого
вiдомий. Пропонується новий екземпляр I ′ задачi Q, отриманий деякими незначними змiна-
ми екземпляра I. Мета реоптимiзацiї при використаннi наближених методiв — застосування
знань про розв’язок початкового екземпляра I для досягнення кращої якостi наближення
(апроксимацiйного вiдношення) екземпляра I ′.
У [11] встановлено порогове вiдношення апроксимацiї для задачi Ins-Max-EkCSP-P (ре-
оптимiзацiя Max-EkCSP-P) з апроксимацiйно-стiйкими предикатами P . У данiй роботi до-
слiджується вiдношення апроксимацiї оптимальних наближених алгоритмiв реоптимiзацiї
задач про узагальнену виконуванiсть з предикатами обмеженої розмiрностi, якi не є апрок-
симацiйно-стiйкими.
Основнi означення i позначення [5, 12]. Пiд предикатом P розмiрностi k розумi-
тимемо вiдображення P : {−1, 1}k → {0, 1}. Для зручностi позначень вхiднi данi зi зна-
ченням −1 iнтерпретуємо як “iстина”, зi значенням 1 — як “хибнiсть”. Якщо предикат P
набуває вхiдного значення y, то P (y) = 1, iнакше — P (y) = 0. Таким чином, множина зна-
чень, що приймається предикатом P , позначається як P−1(1). Лiтерал — це булева змiнна
або її заперечення.
Означення 1. Нехай P : {−1, 1}k → {0, 1} — предикат. Екземпляр задачi Max-CSP-P
складається з m обмежень з вагами, кожне з яких є k-кортеж лiтералiв (zi1 , . . . , zik) з мно-
жини {x1, . . . , xn, x1, . . . , xn}. Всi змiннi в цьому кортежi вважаються рiзними. Обмеження
виконано тодi i тiльки тодi, коли P приймає цей кортеж. Розв’язком екземпляра є припи-
сування значень iстинностi до {x1, . . . , xn}. Значення розв’язку є
m
∑
i=1
P (zi1 , . . . , zik), де wi —
невiд’ємна вага i-го обмеження. Задача полягає в максимiзацiї цього значення. Коли P за-
лежить не бiльше нiж вiд k лiтералiв Max-CSP-P, будемо називати Max-kCSP-P, якщо в P
є k лiтералiв, то — Max-EkCSP-P.
Нехай wopt(I) — значення оптимального розв’язку екземпляра I.
38 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №1
Означення 2. Алгоритм A є C-наближеним для задачi максимiзацiї, якщо для всiх
екземплярiв I задачi w(A, I) > (1/C)wopt(I), де w(A, I) — значення розв’язку алгоритму A
на входi I. При цьому кажуть, що A має апроксимацiйне вiдношення C. Для ймовiрнiсних
алгоритмiв w(A, I) — очiкуване значення (математичне сподiвання).
Введемо предикат XOR(x1, x2) = x1⊕x2. В подальшому як приклад будемо розглядати
задачу Max-Cut.
Означення 3 (Max-Cut). Для даного неорiєнтованого графу G = (V,E) iз множинами
вершин V i ребер E Max-Cut є задачею знаходження розбиття C = (V1, V2) вершин V (V =
= V1
⋃
V2, V1
⋂
V2 = ∅), яке максимiзує число елементiв множини (V1×V2)
⋂
E. Для заданої
вагової функцiї w : E → R+ Max-Cut зважена задача полягає в максимiзацiї
∑
e ∈ (V1 ×
× V2)
⋂
Ew(e).
Розглянемо бiльш детально задачу Max-Cut. Для графу G = (V,E) ця задача (макси-
мальний розрiз в графi) визначається так: знайти таке розбиття множини вершин V на
пiдмножини V1 i V2, щоб максимiзувати число ребер, якi утворюють розрiз. Якщо кожнiй
вершинi поставити у вiдповiднiсть булеву змiнну xi(xi = 1, i ∈ V1, xi = −1, i ∈ V2), то да-
ну задачу можна розглядати як Max-E2CSP-XOR або Max-E2-LIN з рiвняннями вигляду
xixj = −1.
Полiномiальнi оптимальнi (пороговi) наближенi алгоритми для Max-
EkCSP-P задач. Визначимо цiлочисловий розрив αMC SDP релаксацiї Max-Cut: αMC =
= sup
G
{
SDP (G)
OPT (G)
}
, де SDP (G) — оптимум релаксацiї. У роботах [4, 6] показано, що αMC =
=
π
2
1− cos θc
θc
≈ 1,138 (θc — “критичний кут”, на якому досягається максимум).
Розглянемо довiльну невиважену Max-EkCSP-P задачу Z (означення 1, всi ваги дорiв-
нюють 1). Нехай V = {x1, . . . , xn, x1, . . . , xn} — множина змiнних, E — множина обмежень.
Обмеження e ∈ E позначимо як e = (xe1 , . . . , xek), ei ∈ [2n] зi спецiальним порядком на
змiннi (вiдносно V ). Приписування є вiдображення ρ : V → {0, 1}, вiдображення виконує
обмеження e, якщо P (ρ(xe1), . . . , ρ(xek)) = 1. Позначимо OPT (I) оптимальний розв’язок
для екземпляра I задачi Z. Нехай SDP (I) — оптимум напiввизначеної релаксацiї (SDP
релаксацiї) Рагхавендри [12]. Визначимо цiлочисловий розрив αZ = sup
I∈Z
{
SDP (I)
OPT (I)
}
. У [13]
показано, як округлити розв’язок i знайти приписування з апроксимацiйним вiдношенням,
близьким до αZ . Результат Рагхавендри [12] в даному випадку можна навести у виглядi
теореми.
Теорема 1 [8]. Припустимо, iснує екземпляр I∗ Max-EkCSP-P задачi Z такий, що
SDP (I) > c й OPT (I) 6 s(αZ = c/s). Тодi для будь-якого γ > 0 iснують ε, δ > 0 i по-
лiномiальна зведенiсть вiд екземпляра унiкальної iгрової задачi до екземпляра I задачi Z
така, що:
(випадок-так): якщо OPT (U) > 1 − ε, то OPT (I) > c − γ;
(випадок-нi): якщо OPT (U) 6 δ, то OPT (I) 6 s + γ.
Зокрема, припускаючи UGC є NP-складним, апроксимувати Z з вiдношенням, строго
меншим αZ .
Наслiдок. Для будь-якої Max-EkCSP-P задачi Zпри виконаннi UGC iснує полiномiаль-
ний пороговий (оптимальний) αZ-наближений алгоритм.
Зауважимо, що теорема 1 трансформує цiлочисловий розрив у розрив неапроксимова-
ностi. Цiннiсть результату Рагхавендри полягає в тому, що навiть не знаючи явно точного
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №1 39
значення цiлочислового розриву, можна встановити оптимальнiсть вiдповiдного полiномi-
ального наближеного алгоритму (використовуючи екземпляри цiлочислового розриву).
Полiномiальнi оптимальнi (пороговi) наближенi алгоритми для реоптимiзацiї
Max-EkCSP-P задач. Розглянемо довiльну невиважену Max-EkCSP-P задачу Z (озна-
чення 1).
Нехай V = {x1, . . . , xn, x1, . . . , xn} — множина змiнних, екземпляр I задачi Z такий,
що E = {e(1), . . . , e(m)} — множина з m обмежень. Обмеження e(j) ∈ E позначимо як
e(j) = (x
e
(j)
1
, . . . , x
e
(j)
k
), e
(j)
i ∈ [2n](1 6 j 6 m, 1 6 i 6 k) зi спецiальним порядком на змiн-
нi (вiдносно V ). Екземпляр I ′ задачi отримується з екземпляра I додаванням довiльного
(m + 1)-го обмеження e(m+1) (такої самої структури, як i e(j), 1 6 j 6 m). Визначимо ре-
оптимiзацiйний варiант задачi Max-EkCSP-P.
Задача Ins-Max-EkCSP-P. Вхiднi данi. Довiльний екземпляр I задачi Max-EkCSP-P,
x∗ — оптимальний розв’язок екземпляра I.
Результат. Знайти оптимальний розв’язок екземпляра I ′ (отриманого, виходячи з I,
як описано вище) задачi Max-EkCSP-P, використовуючи x∗.
Мета. Знайти x, яке максимiзує число виконаних обмежень екземпляра I ′.
Оскiльки задача Max-EkCSP-P є NP-складною, то можна показати, що такою буде i Ins-
Max-EkCSP-P.
Теорема 2. Якщо k = O(log n) i для задачi Max-EkCSP-P iснує полiномiальний ρ-наб-
лижений алгоритм, то для задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-EkCSP-P) iснує
полiномiальний ψ(ρ)-наближений алгоритм, де ψ(ρ) = 2 − 1/ρ.
Теорема 3. Нехай для задачi Max-EkCSP-P iснує полiномiальний оптимальний (по-
роговий) ρ-наближений алгоритм, а для задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-
EkCSP-P) — полiномiальний γ-наближений алгоритм, тодi γ > ψ(ρ).
Теорема 4. Якщо для задачi Max-EkCSP-P iснує полiномiальний оптимальний (поро-
говий) ρ-наближений алгоритм i k = O(log n), то для задачi Ins-Max-EkCSP-P (реопти-
мiзацiя Max-EkCSP-P) iснує полiномiальний оптимальний (пороговий) ψ(ρ)- наближений
алгоритм, де ψ(ρ) = 2 − 1/ρ.
Теорема 5. Припустимо, що має мiсце унiкальна iгрова гiпотеза UGC. Нехай Z —
довiльна невиважена Max-EkCSP-P задача з цiлочисловим розривом αZ = sup
I∈Z
{
SDP (I)
OPT (I)
}
i k = const. Тодi для задачi Ins-Max-EkCSP-P (реоптимiзацiя Max-EkCSP-P) iснує полiно-
мiальний оптимальний (пороговий) ψ(αZ)-наближений алгоритм, де ψ(αZ) = 2− 1/αZ .
Приклад. Розглянемо задачу Max-Cut. В наших позначеннях це буде задача Max-
E2CSP-XOR, а реоптимiзацiйний варiант — задача Ins-Max-E2CSP-XOR, отримана дода-
ванням довiльного ребра до Max-Cut. Згiдно з [4, 6], цiлочисловий розрив SDP релаксацiї
задачi Max-Cut дорiвнює αMC =
π
2
1− cos θc
θc
≈ 1,138. Тодi з теореми 5 випливає
Теорема 6. Якщо має мiсце унiкальна iгрова гiпотеза UGC, то для задачi Ins-Max-
E2CSP-XOR (реоптимiзацiя Max-Cut) iснує полiномiальний оптимальний (пороговий)
ψ(αMC)-наближений алгоритм, де ψ(αMC) = 2 − 1/αMC ≈ 1,121.
Таким чином, результати цiєї роботи iстотно залежать вiд iстинностi унiкальної iгрової
гiпотези UGC. Поряд iз задачами взаємовiдношень класiв складностi задач за включен-
ням (наприклад, P
?
6= NP ) це одна з основних вiдкритих проблем сучасної теоретичної
iнформатики.
40 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2013, №1
1. Arora S., Lund C., Motwani R. et al. Proof verification and intractability of approximation problems //
J. of the ACM. – 1998. – 45, No 3. – P. 501–555.
2. Goldreich O., Goldwasser S., Ron D. Property testing and its connection to learning and approximation
abstract // Ibid. – 1998. – 45, No 4. – P. 653–750.
3. Goemans M.X., Williamson D.P. Improved approximation algorithms for maximum cut and satisfiability
problems using semidefinite programming // Ibid. – 1995. – 42. – P. 1115–1145.
4. Goemans M.X., Williamson D. P. P. 0.878 approximation algorithms for MAX-CUT and MAX-2SAT //
STOC. – 1994. – P. 422–431.
5. Hastad J. Some optimal inapproximability results // J. of the ACM. – 2001. – 48, No 4. – P. 798–859.
6. Feige U., Schechtman G. On the integrality ratio of semidefinite relaxations of max cut // STOC. – 2001. –
P. 433–442.
7. Khot S. On the power of unique 2-prover 1-round games // Ibid. – 2002. – P. 767–775.
8. Khot S. On the unique games conjecture // Proc. of the 25-th Annual IEEE Conf. on Computational
Complexity. – 2010. – P. 99–121.
9. Khot S., Kindler G., Mossel E., O’Donnell R. Optimal inapproximability results for Max-Cut and other
2-variable CSPs? // FOCS. – 2004. – P. 146–154.
10. Archetti C., Bertazzi L., Speranza M.G. Reoptimizing the travelling salesman problem // Networks. –
2003. – 42(3). – P. 154–159.
11. Михайлюк В.А., Сергиенко И.В. Реоптимизация обобщенных задач о выполнимости с аппроксима-
ционно-устойчивыми предикатами // Кибернетика и систем. анализ. – 2012. – 47, № 1. – С. 89–104.
12. Raghavendra P. Optimal algorithms and inapproximability results for every csp? // Proc. ACM Symp. on
the Theory of Computing (STOC). – 2008. – P. 245–254.
13. Raghavendra P., Steurer D. How to round any csp? // Proc. Annual IEEE Symposium on Foundations of
Computer Science (FOCS). – 2009. – P. 586–594.
Надiйшло до редакцiї 21.05.2012Iнститут кiбернетики iм. В.М. Глушкова
НАН України, Київ
В.А. Михайлюк
Полиномиальная пороговая реоптимизация задач об обобщенной
выполнимости с предикатами ограниченной размерности
При выполнении уникальной игровой гипотезы для решения задачи Ins-Max-EkCSP-P (ре-
оптимизация Max-EkCSP-P при добавлении произвольного ограничения) при k = const су-
ществует полиномиальный оптимальный (пороговый) ψ(αZ)-приближенный алгоритм, где
ψ(αZ) = 2 − 1/αZ и αZ — целочисленный разрыв полуопределенной (SDP) релаксации Max-
EkCSP-P задачи Z.
V.O. Mikhailyuk
Polynomial threshold reoptimization of generalized satisfiability
problems with bounded arity predicates
When the unique game conjecture is hold for the problem Ins-Max-EkCSP-P (reoptimization of
Max-EkCSP-P under insertion of any constraint), an polynomial optimal (threshold) ψ(αZ)-appro-
ximation algorithm exists, where ψ(αZ) = 2− 1/αZ, k = const, and αZ is the integrality gap of a
semidefinite relaxation of the Max-EkCSP-P problem Z.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2013, №1 41
|