Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
При виконанн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вви...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2013 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/85358 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862640980995342336 |
|---|---|
| author | Михайлюк, В.О. |
| author_facet | Михайлюк, В.О. |
| citation_txt | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| 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.
|
| first_indexed | 2025-12-01T04:31:32Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-85358 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | Ukrainian |
| last_indexed | 2025-12-01T04:31:32Z |
| publishDate | 2013 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.О. 2015-07-28T14:09:50Z 2015-07-28T14:09:50Z 2013 Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/85358 519.854 При виконанн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. uk Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності Полиномиальная пороговая реоптимизация задач об обобщенной выполнимости с предикатами ограниченной размерности Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates Article published earlier |
| spellingShingle | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності Михайлюк, В.О. Інформатика та кібернетика |
| title | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_alt | Полиномиальная пороговая реоптимизация задач об обобщенной выполнимости с предикатами ограниченной размерности Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates |
| title_full | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_fullStr | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_full_unstemmed | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_short | Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| title_sort | поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85358 |
| work_keys_str_mv | AT mihailûkvo polínomíalʹnaporogovareoptimízacíâzadačprouzagalʹnenuvikonuvanístʹzpredikatamiobmeženoírozmírností AT mihailûkvo polinomialʹnaâporogovaâreoptimizaciâzadačobobobŝennoivypolnimostispredikatamiograničennoirazmernosti AT mihailûkvo polynomialthresholdreoptimizationofgeneralizedsatisfiabilityproblemswithboundedaritypredicates |