Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2
Припустимо, що виконується унікальна ігрова гіпотеза (UGC). Тоді для реоптимізації Max Cut (при добавленні довільного ребра) існує поліноміальний пороговий (оптимальний) φ(αGW)-наближений алгоритм, де φ(αGW)=1/(2−αGW)≈0,891716, при цьому αGW≈0,878567 (константа Гоеманса–Уільямсона). Для реоптимізаці...
Saved in:
| Date: | 2012 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Видавничий дім "Академперіодика" НАН України
2012
|
| Series: | Доповіді НАН України |
| 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 |
| fulltext |
|
| spelling |
nasplib_isofts_kiev_ua-123456789-500072025-02-23T19:19:44Z Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 Реоптимизация обобщенных проблем об обобщенной выполнимости с предикатами размерности 2 Reoptimization of constraint satisfaction problems with predicates of arity 2 Сергієнко, І.В. Михайлюк, В.О. Інформатика та кібернетика Припустимо, що виконується унікальна ігрова гіпотеза (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). 2012 Article Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/50007 519.854.33 uk Доповіді НАН України application/pdf Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Сергієнко, І.В. Михайлюк, В.О. Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 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 (константа Левіна–Лівната–Звіка). |
| format |
Article |
| author |
Сергієнко, І.В. Михайлюк, В.О. |
| author_facet |
Сергієнко, І.В. Михайлюк, В.О. |
| author_sort |
Сергієнко, І.В. |
| title |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_short |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_full |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_fullStr |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_full_unstemmed |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| title_sort |
реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2012 |
| topic_facet |
Інформатика та кібернетика |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50007 |
| citation_txt |
Реоптимізація проблем про узагальнену виконуваність з предикатами розмірності 2 / I.В. Сергiєнко, В.О. Михайлюк // Доп. НАН України. — 2012. — № 6. — С. 39-46. — Бібліогр.: 15 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT sergíênkoív reoptimízacíâproblemprouzagalʹnenuvikonuvanístʹzpredikatamirozmírností2 AT mihajlûkvo reoptimízacíâproblemprouzagalʹnenuvikonuvanístʹzpredikatamirozmírností2 AT sergíênkoív reoptimizaciâobobŝennyhproblemobobobŝennojvypolnimostispredikatamirazmernosti2 AT mihajlûkvo reoptimizaciâobobŝennyhproblemobobobŝennojvypolnimostispredikatamirazmernosti2 AT sergíênkoív reoptimizationofconstraintsatisfactionproblemswithpredicatesofarity2 AT mihajlûkvo reoptimizationofconstraintsatisfactionproblemswithpredicatesofarity2 |
| first_indexed |
2025-11-24T15:57:58Z |
| last_indexed |
2025-11-24T15:57:58Z |
| _version_ |
1849687936663027712 |