Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності

При виконанн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ввизначеної...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Доповіді НАН України
Datum:	2013
1. Verfasser:	Михайлюк, В.О.
Format:	Artikel
Sprache:	Ukrainian
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

id	nasplib_isofts_kiev_ua-123456789-85358
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
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
spellingShingle	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності Михайлюк, В.О. Інформатика та кібернетика
title_short	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
title_full	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
title_fullStr	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
title_full_unstemmed	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
title_sort	поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності
author	Михайлюк, В.О.
author_facet	Михайлюк, В.О.
topic	Інформатика та кібернетика
topic_facet	Інформатика та кібернетика
publishDate	2013
language	Ukrainian
container_title	Доповіді НАН України
publisher	Видавничий дім "Академперіодика" НАН України
format	Article
title_alt	Полиномиальная пороговая реоптимизация задач об обобщенной выполнимости с предикатами ограниченной размерности Polynomial threshold reoptimization of generalized satisfiability problems with bounded arity predicates
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.
issn	1025-6415
url	https://nasplib.isofts.kiev.ua/handle/123456789/85358
citation_txt	Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 1. — С. 37-41. — Бібліогр.: 13 назв. — укр.
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
first_indexed	2025-12-01T04:31:32Z
last_indexed	2025-12-01T04:31:32Z
_version_	1850859227615068160

Поліноміальна порогова реоптимізація задач про узагальнену виконуваність з предикатами обмеженої розмірності

Institution

Ähnliche Einträge