О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3
При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3...
Збережено в:
| Дата: | 2012 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Назва видання: | Компьютерная математика |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/84720 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-84720 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-847202015-07-14T03:02:02Z О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 Михайлюк, В.А. Теория и методы оптимизации При выполнении уникальной игровой гипотезы (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. 2012 Article О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. ХХХХ-0003 http://dspace.nbuv.gov.ua/handle/123456789/84720 519.854 ru Компьютерная математика Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Теория и методы оптимизации Теория и методы оптимизации |
| spellingShingle |
Теория и методы оптимизации Теория и методы оптимизации Михайлюк, В.А. О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 Компьютерная математика |
| description |
При выполнении уникальной игровой гипотезы (UGC) для задачи Ins - Max - E3CSP - EQUAL (реоптимизация Max - E3CSP - EQUAL при добавлении одного ограничения) существует полиномиальный оптимальный (пороговый) Φ(αEQU ) - приближенный алгоритм, где αEQU ≈ 0.796 пороговое отношение аппроксимации Max - E3CSP - EQUAL и Φ(αEQU ) = 1 / (2 - αEQU ) ≈ 0.831 . |
| format |
Article |
| author |
Михайлюк, В.А. |
| author_facet |
Михайлюк, В.А. |
| author_sort |
Михайлюк, В.А. |
| title |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_short |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_full |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_fullStr |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_full_unstemmed |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| title_sort |
о пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2012 |
| topic_facet |
Теория и методы оптимизации |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/84720 |
| citation_txt |
О пороге отношения аппроксимации обобщенной задачи о выполнимости с предикатом размерности 3 / В.А. Михайлюк // Компьютерная математика: сб. науч. тр. — 2012. — № 2. — С. 156-164. — Бібліогр.: 12 назв. — рос. |
| series |
Компьютерная математика |
| work_keys_str_mv |
AT mihajlûkva oporogeotnošeniâapproksimaciiobobŝennojzadačiovypolnimostispredikatomrazmernosti3 |
| first_indexed |
2023-10-18T19:29:33Z |
| last_indexed |
2023-10-18T19:29:33Z |
| _version_ |
1796147107586899968 |