Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
|
|
| Creator |
Михайлюк, В.О.
|
|
| Subject |
Інформатика та кібернетика
|
|
| 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. При выполнении уникальной игровой гипотезы для решения задачи 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. |
|
| Date |
2015-07-28T14:09:50Z
2015-07-28T14:09:50Z 2013 |
|
| Type |
Article
|
|
| Identifier |
Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр.
1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/85358 519.854 |
|
| Language |
uk
|
|
| Relation |
Доповіді НАН України
|
|
| Publisher |
Видавничий дім "Академперіодика" НАН України
|
|