О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3
При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2012 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84720 |
| 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: | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-84720 |
|---|---|
| record_format |
dspace |
| spelling |
Михайлюк, В.А. 2015-07-13T16:01:55Z 2015-07-13T16:01:55Z 2012 О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84720 519.854 При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3CSP - EQUAL и Φ(αEQU ) = 1 / (2 - αEQU ) ≈ 0.831 . При виконанні унікальної ігрової гіпотези (UGC) для задачі Ins - Max - E3CSP - EQUAL (реоптимізація Max - E3CSP - EQUAL при добавленні одного обмеження) існує поліноміальний оптимальний (пороговий) Φ(αEQU ) -наближений алгоритм, де αEQU ≈ 0.796 порогове відношення апроксимації Max - E3CSP - EQUAL і Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831. If the unique games conjecture (UGC) is true, for the problem Ins - Max - E3CSP - EQUAL ( reoptimization of Max - E3CSP - EQUAL under insertion of one constraint) polynomial optimal (threshold) Φ(αEQU ) - approximation algorithm exists, where aEQU ≈ 0.796 is the threshold approximation ratio of Max - E3CSP - EQUAL and Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Теория и методы оптимизации О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 Про поріг відношення апроксимації для реоптимізації задачі про узагальнену виконуваність з предикатом розмірності 3 On the threshold of approximation ratio for reoptimization of constraint satisfaction problem with predicate of arity 3 Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| spellingShingle |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 Михайлюк, В.А. Теория и методы оптимизации |
| title_short |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_full |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_fullStr |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_full_unstemmed |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_sort |
о пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| author |
Михайлюк, В.А. |
| author_facet |
Михайлюк, В.А. |
| topic |
Теория и методы оптимизации |
| topic_facet |
Теория и методы оптимизации |
| publishDate |
2012 |
| language |
Russian |
| container_title |
Компьютерная математика |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Про поріг відношення апроксимації для реоптимізації задачі про узагальнену виконуваність з предикатом розмірності 3 On the threshold of approximation ratio for reoptimization of constraint satisfaction problem with predicate of arity 3 |
| description |
При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3CSP - EQUAL и Φ(αEQU ) = 1 / (2 - αEQU ) ≈ 0.831 .
При виконанні унікальної ігрової гіпотези (UGC) для задачі Ins - Max - E3CSP - EQUAL (реоптимізація Max - E3CSP - EQUAL при добавленні одного обмеження) існує поліноміальний оптимальний (пороговий) Φ(αEQU ) -наближений алгоритм, де αEQU ≈ 0.796 порогове відношення апроксимації Max - E3CSP - EQUAL і Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831.
If the unique games conjecture (UGC) is true, for the problem Ins - Max - E3CSP - EQUAL ( reoptimization of Max - E3CSP - EQUAL under insertion of one constraint) polynomial optimal (threshold) Φ(αEQU ) - approximation algorithm exists, where aEQU ≈ 0.796 is the threshold approximation ratio of Max - E3CSP - EQUAL and Φ(αEQU ) =1/ (2 - αEQU ) ≈ 0.831.
|
| issn |
ХХХХ-0003 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/84720 |
| citation_txt |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT mihailûkva oporogeotnošeniâapproksimaciiobobŝennoizadačiovypolnimostispredikatomrazmernosti3 AT mihailûkva proporígvídnošennâaproksimacíídlâreoptimízacíízadačíprouzagalʹnenuvikonuvanístʹzpredikatomrozmírností3 AT mihailûkva onthethresholdofapproximationratioforreoptimizationofconstraintsatisfactionproblemwithpredicateofarity3 |
| first_indexed |
2025-12-07T16:14:18Z |
| last_indexed |
2025-12-07T16:14:18Z |
| _version_ |
1850866724763598848 |