Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2
Припустимо, що виконується унікальна ігрова гіпотеза (UGC). Тоді для реоптимізації Max Cut (при добавленні довільного ребра) існує поліноміальний пороговий (оптимальний) φ(αGW)-наближений алгоритм, де φ(αGW)=1/(2−αGW)≈0,891716, при цьому αGW≈0,878567 (константа Гоеманса–Уільямсона). Для реоптимізаці...
Saved in:
| Published in: | Доповіді НАН України |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50007 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50007 |
|---|---|
| record_format |
dspace |
| spelling |
Сергієнко, І.В. Михайлюк, В.О. 2013-10-02T17:31:08Z 2013-10-02T17:31:08Z 2012 Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/50007 519.854.33 Припустимо, що виконується унікальна ігрова гіпотеза (UGC). Тоді для реоптимізації Max Cut (при добавленні довільного ребра) існує поліноміальний пороговий (оптимальний) φ(αGW)-наближений алгоритм, де φ(αGW)=1/(2−αGW)≈0,891716, при цьому αGW≈0,878567 (константа Гоеманса–Уільямсона). Для реоптимізації Max 2-Sat (при добавленні довільної диз'юнкції) існує поліноміальний пороговий (оптимальний) φ(α^−LLZ)-наближений алгоритм, де φ(α^−LLZ)≈0,943544, при цьому α^−LLZ≈0,940166 (константа Левіна–Лівната–Звіка). Допустим, что выполняется уникальная игровая гипотеза (UGC). Тогда для реоптимизации Max Cut (при вставке произвольного ребра) существует полиномиальный пороговый (оптимальный) φ(αGW)-приближенный алгоритм, где φ(αGW)=1/(2−αGW)≈0,891716, при этом αGW≈0,878567 (константа Гоеманса–Уильямсона). Для реоптимизации Max 2-Sat (при вставке произвольной дизьюнкции) существует полиномиальный пороговый (оптимальный) φ(α^−LLZ)-приближенный алгоритм, где φ(α^−LLZ)≈0,943544, при этом α^−LLZ≈0,940166 (константа Левина–Ливната–Звика). Assume that the Unique Game Conjecture (UGC) is held. Then, for the reoptimization of Max Cut (if a new edge is inserted), a polynomial threshold (optimal) φ(αGW)-approximation algorithm exists, where φ(αGW)=1/(2−αGW)≈0.891716 and αGW≈0.878567 (the Goemans–Williamson constant). For the reoptimization of Max 2-Sat (if a new disjunction is inserted), a polynomial threshold (optimal) φ(α^−LLZ)-approximation algorithm exists, where φ(α^−LLZ)≈0.943544 and α^−LLZ≈0.940166 (the Levin–Livnat–Zwick constant). uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 Реоптимизация обобщенных проблем об обобщенной выполнимости с предикатами размерности 2 Reoptimization of constraint satisfaction problems with predicates of arity 2 Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| spellingShingle |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 Сергієнко, І.В. Михайлюк, В.О. Інформатика та кібернетика |
| title_short |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_full |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_fullStr |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_full_unstemmed |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_sort |
реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| author |
Сергієнко, І.В. Михайлюк, В.О. |
| author_facet |
Сергієнко, І.В. Михайлюк, В.О. |
| topic |
Інформатика та кібернетика |
| topic_facet |
Інформатика та кібернетика |
| publishDate |
2012 |
| language |
Ukrainian |
| container_title |
Доповіді НАН України |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| format |
Article |
| title_alt |
Реоптимизация обобщенных проблем об обобщенной выполнимости с предикатами размерности 2 Reoptimization of constraint satisfaction problems with predicates of arity 2 |
| description |
Припустимо, що виконується унікальна ігрова гіпотеза (UGC). Тоді для реоптимізації Max Cut (при добавленні довільного ребра) існує поліноміальний пороговий (оптимальний) φ(αGW)-наближений алгоритм, де φ(αGW)=1/(2−αGW)≈0,891716, при цьому αGW≈0,878567 (константа Гоеманса–Уільямсона). Для реоптимізації Max 2-Sat (при добавленні довільної диз'юнкції) існує поліноміальний пороговий (оптимальний) φ(α^−LLZ)-наближений алгоритм, де φ(α^−LLZ)≈0,943544, при цьому α^−LLZ≈0,940166 (константа Левіна–Лівната–Звіка).
Допустим, что выполняется уникальная игровая гипотеза (UGC). Тогда для реоптимизации Max Cut (при вставке произвольного ребра) существует полиномиальный пороговый (оптимальный) φ(αGW)-приближенный алгоритм, где φ(αGW)=1/(2−αGW)≈0,891716, при этом αGW≈0,878567 (константа Гоеманса–Уильямсона). Для реоптимизации Max 2-Sat (при вставке произвольной дизьюнкции) существует полиномиальный пороговый (оптимальный) φ(α^−LLZ)-приближенный алгоритм, где φ(α^−LLZ)≈0,943544, при этом α^−LLZ≈0,940166 (константа Левина–Ливната–Звика).
Assume that the Unique Game Conjecture (UGC) is held. Then, for the reoptimization of Max Cut (if a new edge is inserted), a polynomial threshold (optimal) φ(αGW)-approximation algorithm exists, where φ(αGW)=1/(2−αGW)≈0.891716 and αGW≈0.878567 (the Goemans–Williamson constant). For the reoptimization of Max 2-Sat (if a new disjunction is inserted), a polynomial threshold (optimal) φ(α^−LLZ)-approximation algorithm exists, where φ(α^−LLZ)≈0.943544 and α^−LLZ≈0.940166 (the Levin–Livnat–Zwick constant).
|
| issn |
1025-6415 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50007 |
| citation_txt |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр. |
| work_keys_str_mv |
AT sergíênkoív reoptimízacíâproblemprouzagalʹnenuvikonuvanístʹzpredikatamirozmírností2 AT mihailûkvo reoptimízacíâproblemprouzagalʹnenuvikonuvanístʹzpredikatamirozmírností2 AT sergíênkoív reoptimizaciâobobŝennyhproblemobobobŝennoivypolnimostispredikatamirazmernosti2 AT mihailûkvo reoptimizaciâobobŝennyhproblemobobobŝennoivypolnimostispredikatamirazmernosti2 AT sergíênkoív reoptimizationofconstraintsatisfactionproblemswithpredicatesofarity2 AT mihailûkvo reoptimizationofconstraintsatisfactionproblemswithpredicatesofarity2 |
| first_indexed |
2025-11-24T15:57:58Z |
| last_indexed |
2025-11-24T15:57:58Z |
| _version_ |
1850849699495411712 |
| fulltext |
УДК 519.854.33
© 2012
Академiк НАН України I. В. Сергiєнко, В.О. Михайлюк
Реоптимiзацiя проблем про узагальнену виконуванiсть
з предикатами розмiрностi 2
Припустимо, що виконується унiкальна iгрова гiпотеза (UGC). Тодi для реоптимiзацiї
Max Cut (при добавленнi довiльного ребра) iснує полiномiальний пороговий (оптималь-
ний) ϕ(αGW)-наближений алгоритм, де ϕ(αGW) = 1/(2 − αGW) ≈ 0,891716, при цьо-
му αGW ≈ 0,878567 (константа Гоеманса–Уiльямсона). Для реоптимiзацiї Max 2-Sat
(при добавленнi довiльної диз’юнкцiї) iснує полiномiальний пороговий (оптимальний)
ϕ(α−
LLZ
)-наближений алгоритм, де ϕ(α−
LLZ
) ≈ 0,943544, при цьому α−
LLZ
≈ 0,940166 (кон-
станта Левiна–Лiвната–Звiка).
Один клас проблем, який мiстить багато цiкавих i вже добре вивчених задач дискретної
оптимiзацiї, являють собою проблеми про узагальнену виконуванiсть, або CSP проблеми
(Constraint Satisfaction Problems). В таких проблемах є множина з n змiнних i множина
обмежень (що задаються предикатами), кожне з яких залежить вiд деякого числа змiнних,
i мета полягає в тому, щоб знайти такi приписування значень змiнних, якi виконують макси-
мальне число обмежень. Предикати вiд двох змiнних є основними при вивченнi властивос-
тей узагальнених проблем про виконуванiсть. Визначення максимального числа виконаних
обмежень в таких проблемах є NP -складним (NP -жорстким, NP -hard) i така проблема
вiдома як Max 2-CSP. Ця проблема має два частинних найбiльш добре вивчених випадки:
Max Cut i Max 2-Sat проблеми.
Вирiшити NP -складнi оптимiзацiйнi проблеми точно за допустимий час навряд чи мож-
ливо. Тому розглядаються ефективнi наближенi алгоритми для розв’язування таких задач.
Для максимiзацiйної проблеми кажуть, що алгоритм є C-наближеним алгоритмом, якщо
вiн для довiльного екземпляра дає розв’язок зi значенням цiльової функцiї не меншим, нiж
C · OPT , де OPT — глобальний оптимум. При цьому C називають вiдношенням апрокси-
мацiї. Подiбне означення можна дати для мiнiмiзацiйних проблем.
Фундаментальне питання для заданої NP -складної проблеми — це визначити, при яких
значеннях C можна сподiватися на ефективний (полiномiальний) C-наближений алгоритм.
Це велика дослiдницька область у теоретичнiй информатицi зi своїми позитивними та не-
гативними результатами.
Кажуть, що для проблеми Q встановлена верхня оцiнка вiдношення апроксимацiї C,
якщо iснує полiномiальний C-наближений алгоритм для розв’язання Q. Для проблеми Q
встановлена нижня оцiнка вiдношення апроксимацiї c, якщо для довiльного ε > 0 не iснує
полiномiального наближеного алгоритму для Q, на якому досягається вiдношення апрок-
симацiї c + ε (або строго бiльше c). Якщо C = c, то для проблеми Q встановлений порiг
вiдношення апроксимацiї (що дорiвнює C = c). Вiдповiдний алгоритм називається порого-
вим або оптимальним.
Проблема встановлення нижнiх оцiнок вiдношення апроксимацiї (як i довiльна пробле-
ма отримання нижнiх оцiнок складностi) є дуже складною задачею. Для такої проблеми
iснує назва неапроксимованiсть (inapproximability) або складнiсть апроксимацiї (hardness
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №6 39
of approximation). Великий вплив на развиток методiв одержання нижнiх оцiнок здiйснила
знаменита PCP теорема [1] i дискретний аналiз Фур’є для тестування властивостей проб-
лем (property testing) [2].
Поряд зi звичайними детермiнованими алгоритмами розглядають випадковi алгоритми,
де оцiнюється очiкуване значення розв’язку. Протягом десятилiть випадковий алгоритм
для проблем Max Cut i Max 2-Sat був найкращим i тiльки в 1995 р. Гоеманс i Уiльям-
сон (Goemans and Williamson) [3] запропонували 0,87856-наближенi алгоритми для Max
Cut i Max 2-Sat. Вони застосували технiку напiввизначеного програмування (semidefinite
programming, SDP) для знаходження оптимального розв’язку з високою точнiстю (алгоритм
внутрiшньої точки), а потiм “заокруглили” розв’язок до дискретного варiанта початкової
проблеми. Цей пiдхiд потiм був успiшно застосований до iнших комбiнаторних оптимiза-
цiйних проблем.
Як вже вiдзначалося, проблема неапроксимованостi була успiшно розв’язана для ба-
гатьох проблем завдяки PCP теоремi. Зокрема, Хастад (Hastad) [2] показав, що узагаль-
нення Max Cut i Max 2-Sat вiд двох до трьох змiнних, тобто Max-E3-Lin-2 i Max 3-Sat
є NP -складними для апроксимацiї з вiдношеннями 1/2+ ε i 7/8+ ε вiдповiдно. Це означає,
що найпростiший випадковий алгоритм приписування є найкращим для цих проблем, якщо
P 6= NP або що вiдношення 1/2 i 7/8 є пороговими. В [4] показано (також за допомогою
PCP теореми), що задача про покриття множинами має порiг вiдношення апроксимацiї,
який дорiвнює lnn.
При вивченнi проблеми неапроксимованостi для проблем про узагальнену виконуванiсть
з предикатами размiрностi 2 такий прогрес не був досягнутий. Найкращi результати за скла-
днiстю апроксимацiї для Max 2-CSP, Max 2-Sat i Max Cut є вiдповiдно 9/10 + ε ≈ 0,900,
21/22 + ε ≈ 0,955 i 16/17 + ε ≈ 0,941 [2, 5]. Найбiльш перспективний пiдхiд до отриман-
ня сильних результатiв (порогiв вiдношень апроксимацiї) — це так звана унiкальна iгрова
гiпотеза (Unique Games Conjecture, UGC), введена С. Кхотом [6]. UGC — це одна з най-
бiльш важливих вiдкритих проблем у сучаснiй теоретичнiй информатицi завдяки великiй
кiлькостi сильних результатiв з неапроксимованостi, якi випливають з UGC.
Для Max 2-CSP проблем отриманi такi результати. Кхот [7] показав, що з UGC випли-
ває αGW + ε — результат за складнiстю апроксимацiї для Max Cut, де αGW ≈ 0,87856 —
вiдношення апроксимацiї алгоритма Гоеманса–Уiльямсона [3]. В [8, 15] показано, що з UGC
випливає α−
LLZ+ε результат за складнiстю апроксимацiї для Max 2-Sat, де α−
LLZ ≈ 0,94016 —
вiдношення апроксимацiї алгоритма Левiна–Лiвната–Звiка (Lewin–Livnat–Zwick) [9]. Вiдомi
iншi роботи, де найкращi результати з неапроксимованостi, основанi на UGC, збiгаються
з вiдношенням апроксимацiї наближених алгоритмiв, основаних на напiввизначеному про-
грамуваннi.
Поняття реоптимiзацiї [10–12] полягає в наступному. Нехай Q — деяка NP -складна
(можливо, NP -повна) проблема, I — початковий екземпляр проблеми Q, оптимальний
розв’язок якого вiдомо. Пропонується новий екземпляр I ′ задачi Q, отриманий деякими
“незначними” змiнами екземпляра I. Виникає питання: як можна ефективно використати
знання про оптимальний розв’язок I для обчислення точного або наближеного роз’язку
екземпляра I ′? Мета реоптимiзацiї при використаннi наближених методiв — застосування
знань про розв’язання початкового екземпляра I при умовi: або досягнення кращої якос-
тi наближення (апроксимацiйного вiдношення) I ′, або створення бiльш ефективного (за
часом) алгоритму визначення оптимального або близького до нього розв’язку I ′, або вико-
нання першого i другого пунктiв.
40 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №6
Дослiджувалися реоптимiзацiйнi варiанти задач про узагальнену виконуванiсть з пре-
дикатами размiрностi 2.
Основнi означення та позначення. Наведемо необхiднi позначення i означення [2, 13].
П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} є предикат. Екземпляр проблеми 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
wiP (zi1 , . . . , zik), де wi — (невiд’ємна)
вага i-го обмеження. Мета полягає в максимiзацiї цього значення. Коли P залежить вiд
не бiльше нiж k лiтералiв Max-CSP-P , будемо називати Max-kCSP-P , якщо в P рiвно k
лiтералiв — то Max-EkCSP-P .
Нехай wopt(I) — значення оптимального розв’язку екземпляра I.
Означення 2. Алгоритм A є C-наближений алгоритм для максимiзацiйної проблеми,
якщо для всiх екземплярiв I проблеми w(A, I) > Cwopt(I), де w(A, I) — значення розв’язку
алгоритму A на входi I. При цьому кажуть, що A має апроксимацiйне вiдношення C. Для
ймовiрнiсних алгоритмiв w(A, I) — очiкуване значення (математичне сподiвання) серед ви-
падкових виборiв алгоритму A.
У подальшому розглядатимемо випадок k = 2. Введемо предикати AND(x1, x2) = x1 ∧
∧ x2, XOR(x1, x2) = x1 ⊕ x2 i OR(x1, x2) = x1 ∨ x2. Можна показати, що вони описують всi
предикати розмiрностi 2 з точнiстю до еквiвалентностi задач виконуваностi.
Означення 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)∩E
w(e).
Означення 4 (Max 2-Sat). Екземпляр Max 2-Sat проблеми є множина змiнних i множи-
на диз’юнкцiй вiд двох лiтералiв, де лiтерал є змiнна або її заперечення. Проблема полягає
в приписуваннi змiнним значень так, що число виконаних диз’юнкцiй максимально. Для за-
даної невiд’ємної вагової функцiї над множиною диз’юнкцiй Max 2-Sat проблема з вагами
полягає в максимiзацiї сум вагiв всiх виконаних диз’юнкцiй.
Згiдно з введеним означенням, проблема Max 2-Sat у нашому випадку буде позначатися
як Max-E2CSP-OR, а проблема Max Cut — як Max-E2CSP-XOR.
Напiввизначене програмування (SDP) i проблеми Max Cut та Max 2-Sat.
Основна технiка для отримання ефективних наближених алгоритмiв для Max-CSP-P —
це напiввизначене програмування, запропоноване Гоемансом та Уiльямсоном [3]. Оскiльки
базовий алгоритм є красивим i досить простим для Max Cut, наведемо його коротко.
Формалiзуємо Max Cut як задачу квадратичного цiлочислового програмування:
max
x∈{−1,1}n
∑
(i,j)∈E
1− xixj
2
. (1)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №6 41
Ця сума точно вiдповiдає розмiру максимального розрiзу, оскiльки кожний терм 1, якщо
ребро належить розрiзу, i 0 — iнакше. Послабимо (1) введенням змiнних yij для добуткiв
xixj, отримаємо
max
y
∑
(i,j)∈E
1− yij
2
.
Припустимо, що змiннi yij формують додатну симетричну напiввизначену матрицю
з одиницями на дiагоналi. Запишемо це таким чином:
max
y>0, yii=1
∑
(i,j)∈E
1− yij
2
. (2)
Вiдзначимо, що це релаксацiя початкової проблеми, оскiльки yij = xixj i, дiйсно, матри-
ця задовольняє умови. Оптимiзацiйна проблема (2) може бути розв’язана полiномiальним
алгоритмом внутрiшньої точки з довiльною точнiстю. Для простоти будемо вважати, що
знайдений точний оптимум. Запишемо (2) iнакше. Вiдомо, що n×n-матриця Y симетрично
додатно напiввизначена тодi i тiльки тодi, коли iснує iнша n × n-матриця V така, що Y =
= V TV . Звiдси випливає, що знайдуться вектори (стовпцi V ) такi, що yij = (vi, vj) i вимога
yii = 1 еквiвалентна тому, що vi — одиничний вектор. Таким чином, (2) еквiвалентно
max
(‖vi‖=1)n
i=1
∑
(i,j)∈E
1− (vi, vj)
2
. (3)
У такiй постановцi (3) — строге узагальнення (1), оскiльки можна iнтерпретувати xi як
одиничний вектор. В цьому разi розв’язок з високою розмiрнiстю використовується для ви-
значення розв’язку розмiрностi 1. Пропонується така процедура заокруглення з використан-
ням випадкової гiперплощини. Нормальнi вектори цих випадкових гiперплощин рiвномiрно
разподiленi на n-вимiрнiй сферi. Отже, вектор r ∈ R
n вибираємо випадково i рiвномiрно
i покладемо xi = sign((r, vi)) (при (r, vi) = 0 покладемо xi = 1).
Проаналiзуємо цю процедуру заокруглення. Припустимо кут мiж vi i vj є θij. Тодi внесок
в цiльову функцiю буде (1 − cos θij)/2, а ймовiрнiсть, що ребро належить розрiзу, тобто
sign((r, vi)) 6= sign((r, vj)) є θij/π. Визначимо дiйсне число αGW так:
αGW = min
06θ6π
θ/π
(1− cos θ)/2
.
Числове значення αGW приблизно дорiвнює 0,87856. Маємо такий ланцюжок нерiвно-
стей:
E
[
∑
(i,j)∈E
1− xixj
2
]
=
∑
(i,j)∈E
θij
π
> αGW
∑
(i,j)∈E
1− cos θij
2
> αGWOPT.
Остання нерiвнiсть випливає з того, що максимум релаксацiї не менший, нiж дiйсний
максимум. Таким чином, даний алгоритм є αGW-наближеним алгоритмом.
Аналогiчно будується SDP релаксацiя Max 2-Sat (або Max-E2 CSP-OR). Задача розв’я-
зується з аддитивною вiдносною помилкою ε за час, полiномiальний вiд log 1/ε [14]. Для
42 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №6
технiки заокруглення застосовуються цiлi схеми (конфiгурацiї) заокруглення, якi зале-
жать вiд вибору функцiї заокруглення. В результатi був отриманий α−
LLZ-наближений алго-
ритм [9, 8] для розв’язання Max 2-Sat, де |α−
LLZ−0,94016567245| 6 5 ·10−11 (слiд вiдзначити,
що для визначення α−
LLZ використовувався чисельний алгоритм; аналiтичнi доведення не
були наведенi).
Унiкальна iгрова гiпотеза (UGC). UGC була введена Кхотом (Khot) [6] як можли-
вий спосiб одержання нових сильних результатiв з неапроксимованостi. Сформулюємо цю
гiпотезу в термiнах проблеми про покриття мiток (Label Cover problem).
Означення 5. Екземпляр X = (V,E,w, [L], {σv
e , σ
w
e }e={v,w}∈E) унiкальної проблеми про
покриття мiток (Unique Label Cover, ULC) визначається таким чином: заданий граф G =
= (V,E) з ваговою функцiєю w : E → [0, 1], множина [L] = {1, 2, . . . , L} допустимих мiток
i для кожного ребра e = {v,w} ∈ E двi перестановки σv
e , σ
w
e ∈ ΣL такi, що σw
e = (σv
e )
−1,
тобто вони взаємно оберненi. Будемо говорити, що функцiя ℓ : V → [L] (яка називається
маркiровкою вершин) задовольняє ребро e = (v,w), якщо σv
e (ℓ(v)) = ℓ(w) або еквiвалент-
но, якщо σw
e (ℓ(w)) = ℓ(v). Значення ℓ — це загальна вага ребер, якi вона задовольняє,
тобто V alX(ℓ) =
∑
e
w(e), де сума береться по всiх e так, що ℓ задовольняє e. Значення X
є максимальна частина ребер, що задовольняються, за всiма маркiровками, тобто V al(X) =
= max
ℓ
{V alX(ℓ)}.
ULC проблема, де G — дводольний граф, може бути iнтерпретована як однораундова
гра двох гравцiв, в якiй приймаючий предикат перевiряючого такий, що для даної вiдповiдi
одного з гравцiв завжди iснує унiкальна вiдповiдь для iншого гравця така, що перевiряючий
приймає. Ймовiрнiсть, що перевiряючий приймає, якщо гравцi притримуються оптимальної
стратегiї, тодi дорiвнює V al(X). Звiдси термiн “унiкальна iгрова гiпотеза”. Будемо притри-
муватися розривної версiї ULC проблеми (gap version), яку можна визначити так.
Означення 6. Gap − ULCη,γ,L є проблема для даного екземпляра X ULC проблеми
з множиною мiток [L] визначити: або V al(X) > 1 − η, або V al(X) 6 γ.
Унiкальна iгрова гiпотеза (UGC) [8]. Для довiльних η > 0, γ > 0 iснує константа
L > 0 така, що Gap − ULCη,γ,L є NP -складною.
Таким чином, UGC стверджує, що розривна версiя ULC важкорозв’язна для довiльних
достатньо малих η i γ з достатньо великим L.
Справедливi такi результати.
Теорема 1 [3]. Припустимо, що справедлива унiкальна iгрова гiпотеза (UGC). Тодi для
довiльного −1 < ρ < 0 i ε > 0 є NP -складним вiдрiзнити екземпляри Max Cut, якi не менше
нiж ((1 − ρ)/2)-виконанi, вiд екземплярiв, якi не бiльше нiж ((arccos ρ)/π + ε)-виконанi.
Зокрема, вибираючи ρ = ρ∗, де
ρ∗ = argmin
−1<ρ<0
arccos ρ
π
1
2
−
1
2
ρ
≈ −0,689,
отримаємо, що NP -складно апроксимувати Max Cut з довiльним вiдношенням, бiльшим,
нiж αGW ≈ 0,878567.
Оскiльки αGW = min
−1<ρ<0
{
(arccos ρ)/π
(1− ρ)/2
}
= min
06θ6π
{
θ/π
(1− cos θ)/2
}
, то оптимальний ви-
бiр θ — розв’язок рiвняння θ = tg(θ/2), θ∗ ≈ 2,33 ≈ 134◦, αGW = 2/(π sin θ∗).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №6 43
Теорема 2 [8]. Припустимо, що справедлива унiкальна iгрова гiпотеза (UGC). Тодi
для довiльного ε > 0 є NP -складним апроксимувати Max 2-Sat з вiдношенням, не меншим
нiж α−
LLZ+ ε, де α−
LLZ ≈ 0,94017 (апроксимацiйне вiдношення алгоритму Левiна–Лiтвана–
Звiка).
Згiдно з теоремою 1, можна стверджувати, що, приймаючи UGC, вiдношення апрокси-
мацiї αGW є пороговим для проблеми Max Cut (алгоритм Гоеманса–Уiльямсона — оптималь-
ний). Те ж саме можна стверджувати (згiдно з теоремою 2) щодо вiдношення апроксимацiї
α−
LLZ. Воно є пороговим для Max 2-Sat (алгоритм Левiна–Лiтвана–Звiка — оптимальний).
Порiг вiдношення апроксимацiї для реоптимiзацiї Max Cut i Max 2-Sat. Нехай
Max-E2CSP-P довiльна безвагова CSP проблема з m обмеженнями (wi = 1, i ∈ [m]). Не-
хай I — довiльний екземпляр проблеми Max-E2CSP-P , екземпляр I ′ проблеми отримається
з екземпляра I добавленням довiльного (m + 1)-го обмеження z(m+1) = (z
(m+1)
i1
, z
(m+1)
i2
)
(z
(m+1)
ij
∈ {x1, . . . , xn, x1, . . . , xn}, j = 1, 2). Визначимо реоптимiзацiйний варiант проблеми
Max-E2CSP-P .
Проблема Ins-Max-E2CSP-P . Вхiднi данi. Довiльний екземпляр Iпроблеми Max-
E2CSP-P , x∗ — оптимальний розв’язок екземпляра I.
Результат. Знайти оптимальний розв’язок екземпляра I ′ (отриманого, виходячи з I, як
описано вище) проблеми Max-E2CSP-P , використовуючи x∗.
Мета. Знайти x, яке максимiзує число виконаних обмежень екземпляра I ′.
Оскiльки Max-E2CSP-P є NP -складною, то можна показати, що такою буде
i Max-E2CSP-P .
Теорема 3. Якщо для проблеми Max-E2CSP-P iснує полiномiальний ρ-наближений
алгоритм, то для проблеми Ins-Max-E2CSP-P (реоптимiзацiя Max-E2CSP-P ) iснує полi-
номiальний ϕ(ρ)-наближений алгоритм, де ϕ(ρ) = 1/(2 − ρ).
Теорема 4. Якщо для проблеми Max-E2CSP-P iснує полiномiальний пороговий (опти-
мальний) ρ-наближений алгоритм, а для проблеми Ins-Max-E2CSP-P (реоптимiзацiя
Max-E2CSP-P ) iснує полiномiальний γ-наближений алгоритм, то γ 6 ϕ(ρ).
З теорем 3 та 4 випливає теорема 5.
Теорема 5. Якщо для проблеми Max-E2CSP-P iснує полiномiальний пороговий (опти-
мальний) ρ-наближений алгоритм, то для проблеми Ins-Max-E2CSP-P (реоптимiзацiя
Max-E2CSP-P ) iснує полiномiальний пороговий (оптимальний) ϕ(ρ)-наближений алго-
ритм, де ϕ(ρ) = 1/(2 − ρ).
Теорема 6. Припустимо, що справедлива унiкальна iгрова гiпотеза (UGC). Тодi для
проблеми Ins-Max-E2CSP-P (реоптимiзацiя Max Cut) iснує полiномiальний пороговий (оп-
тимальний) ϕ(αGW)-наближений алгоритм, де ϕ(αGW ) = 1/(2 − αGW ).
Теорема 7. Припустимо, що справедлива унiкальна iгрова гiпотеза (UGC). Тодi для
проблеми Ins-Max-E2 CSP-OR (реоптимiзацiя Max 2-Sat) iснує полiномiальний пороговий
(оптимальний) ϕ(α−
LLZ)-наближений алгоритм, де ϕ(α−
LLZ) = 1/(2 − α−
LLZ).
Згiдно з теоремою 6, порiг вiдношення апроксимацiї для реоптимiзацiї Max Cut(при до-
бавленнi довiльного ребра в граф) дорiвнює ϕ(αGW) ≈ 0,891716. Згiдно з теоремою 7, порiг
вiдношення апроксимацiї для реоптимiзацiї Max 2-Sat (при добавленнi довiльної диз’юнк-
цiї) дорiвнює ϕ(α−
LLZ) ≈ 0,943544.
Таким чином, в роботi показано, що при виконаннi унiкальної iгрової гiпотези (UGC) для
реоптимiзацiї Max Cut (при добавленнi довiльного ребра в граф) i для реоптимiзацiї Max
2-Sat (при добавленнi довiльної диз’юнкцiї) iснують полiномiальнi пороговi (оптимальнi)
44 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №6
наближенi алгоритми. Результати цiєї роботи iстотно залежать вiд iстиностi UGC. Поряд
з проблемами взаємовiдношення класiв складностi проблем з включення (наприклад, P 6=
6= NP?) це одна з основних вiдкритих проблем сучасної теоретичної iнформатики. Навiть
якщо UGC хибна, може виявитися, що Gap = ULCη,γ,L складна в сенсi нерозв’язностi за
полiномiальний час i така (слабка) складнiсть може бути застосована до всiх проблем, де
складнiсть демонструвалася, виходячи з UGC.
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. Hastad J. Some optimal inapproximability results // Ibid. – 2001. – 48, No 4. – P. 798–859.
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. Feige U. A threshold of lnn for approximating set cover // Ibid. – 1998. – 45, No 4. – P. 634–652.
5. Trevisan L., Sorkin D. B., Sudan M. Gadgets, approximation, and linear programming // SIAM J. on
Computing. – 2000. – 29, No 6. – P. 2074. – 2097.
6. Khot S. On the power of unique 2-prover 1-round games // Sympos. Theory of Comput. – 2002. – P. 767–
775.
7. Khot S., Kindler G., Mossel E., O’Donnell R. Optimal inapproximability results for Max-Cut and other
2-variable CSPs? // Sympos. Found. of Comput. Sci. – 2004. – P. 146–154.
8. Austrin P. Balanced Max 2-Sat might not be the hardest // Sympos. Theory of Comput. – 2007. –
P. 189–197.
9. Lewin M., Livnat D., Zwick U. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT
problems // Lecture Notes in Computer Science. – 2002. – 2337. – P. 67–82.
10. Bockenhauer H. J., Hromkovic J., Momke T., Widmayer P. On the hardness of reoptimization // Proc. of
the 34 th Intern. Conf. on Current Trends in Theory and Practice of Computer Science (SOF-SEM 2008);
Lect. Notes Comput. Sci. – Springer: Berlin, 2008. – 4910. – P. 50–65.
11. Ausiello G., Bonifaci V., Escoffier B. Complexity and approximation in reoptimization // Computability
in Context: Computation and Logic in the Real World / Ed. S.B. Cooper and A. Sorbi). – London: Imperial
College Press, 2011. – P. 101–130.
12. Михайлюк В.А. Реоптимизация задачи о покрытии множествами // Кибернетика и систем. анализ. –
2010. – 46, № 6. – С. 27–31.
13. Hast G. Beating a random assignment: Doctoral Thesis. – Stockholm: Royal Institute of Technology, 2005. –
102 p.
14. Alizadeh F. Interior point methods in semidefinite programming with applications to combinatorial opti-
mization // SIAM J. on Optimization. – 1995. – 5. – P. 13–51.
15. Austrin P. Towards sharp inapproximability for any 2-CSP // Sympos. Found. of Comput. Sci. – 2007. –
P. 307–317.
Надiйшло до редакцiї 12.10.2011Iнститут кiбернетики iм. В.М. Глушкова
НАН України, Київ
Академик НАН Украины И.В. Сергиенко, В.А. Михайлюк
Реоптимизация обобщенных проблем об обобщенной выполнимости
с предикатами размерности 2
Допустим, что выполняется уникальная игровая гипотеза (UGC). Тогда для реоптими-
зации Max Cut (при вставке произвольного ребра) существует полиномиальный пороговый
(оптимальный) ϕ(αGW)-приближенный алгоритм, где ϕ(αGW) = 1/(2 − αGW ) ≈ 0,891716,
при этом αGW ≈ 0,878567 (константа Гоеманса–Уильямсона). Для реоптимизации Max
2-Sat (при вставке произвольной дизьюнкции) существует полиномиальный пороговый (оп-
тимальный) ϕ(α−
LLZ
)-приближенный алгоритм, где ϕ(α−
LLZ
) ≈ 0,943544, при этом α−
LLZ
≈
≈ 0,940166 (константа Левина–Ливната–Звика).
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2012, №6 45
Academician of the NAS of Ukraine I.V. Sergienko, V. A. Mikhailyuk
Reoptimization of constraint satisfaction problems with predicates of
arity 2
Assume that the Unique Game Conjecture (UGC) is held. Then, for the reoptimization of Max Cut
(if a new edge is inserted), a polynomial threshold (optimal) ϕ(αGW) — approximation algorithm
exists, where ϕ(αGW) = 1/(2−αGW) ≈ 0.891716 and αGW ≈ 0.878567 (the Goemans–Williamson
constant). For the reoptimization of Max 2-Sat (if a new disjunction is inserted), a polynomial
threshold (optimal) ϕ(α
|−|
LLZ
) — approximation algorithm exists, where ϕ(α−
LLZ
) ≈ 0.943544 and
α−
LLZ
≈ 0.940166 (the Levin–Livnat–Zwick constant).
46 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2012, №6
|