Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости

При виконанні унікальної ігрової гіпотези (UGC) для реоптимізації строгих узагальнених задач про виконуваність (при включенні довільного обмеження) існує оптимальний наближений алгоритм. Відношення апроксимації цього алгоритму залежить від цілочисельного розриву лінійної релаксації вихідної задачі....

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Проблемы управления и информатики
Datum:2012
1. Verfasser: Михайлюк, В.А.
Format: Artikel
Sprache:Russisch
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Schlagworte:
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/207540
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:Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 6. — С. 44–53. — Бібліогр.: 18 назв. - рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1862667165022289920
author Михайлюк, В.А.
author_facet Михайлюк, В.А.
citation_txt Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 6. — С. 44–53. — Бібліогр.: 18 назв. - рос.
collection DSpace DC
container_title Проблемы управления и информатики
description При виконанні унікальної ігрової гіпотези (UGC) для реоптимізації строгих узагальнених задач про виконуваність (при включенні довільного обмеження) існує оптимальний наближений алгоритм. Відношення апроксимації цього алгоритму залежить від цілочисельного розриву лінійної релаксації вихідної задачі. Assume that Unique Games Conjecture (UGC) is hold. Then for reoptimization of strict constraint satisfaction problems (under insertion of any constraint) there exists the optimal approximation algorithm. The approximation ratio of this algorithm depends on integral gap of linear relaxation of the original problem.
first_indexed 2025-12-07T15:21:34Z
format Article
fulltext
id nasplib_isofts_kiev_ua-123456789-207540
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 0572-2691
language Russian
last_indexed 2025-12-07T15:21:34Z
publishDate 2012
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
record_format dspace
spelling Михайлюк, В.А.
2025-10-09T11:40:23Z
2012
Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 6. — С. 44–53. — Бібліогр.: 18 назв. - рос.
0572-2691
https://nasplib.isofts.kiev.ua/handle/123456789/207540
519.854
10.1615/JAutomatInfScien.v44.i11.40
При виконанні унікальної ігрової гіпотези (UGC) для реоптимізації строгих узагальнених задач про виконуваність (при включенні довільного обмеження) існує оптимальний наближений алгоритм. Відношення апроксимації цього алгоритму залежить від цілочисельного розриву лінійної релаксації вихідної задачі.
Assume that Unique Games Conjecture (UGC) is hold. Then for reoptimization of strict constraint satisfaction problems (under insertion of any constraint) there exists the optimal approximation algorithm. The approximation ratio of this algorithm depends on integral gap of linear relaxation of the original problem.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Проблемы управления и информатики
Оптимальное управление и методы оптимизации
Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
Оптимальний наближений алгоритм реоптимізації для строгих узагальнених задач про виконуваність
Optimal Approximation Algorithm for Reoptimization of Strict Constraint Satisfaction Problems
Article
published earlier
spellingShingle Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
Михайлюк, В.А.
Оптимальное управление и методы оптимизации
title Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
title_alt Оптимальний наближений алгоритм реоптимізації для строгих узагальнених задач про виконуваність
Optimal Approximation Algorithm for Reoptimization of Strict Constraint Satisfaction Problems
title_full Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
title_fullStr Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
title_full_unstemmed Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
title_short Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
title_sort оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
topic Оптимальное управление и методы оптимизации
topic_facet Оптимальное управление и методы оптимизации
url https://nasplib.isofts.kiev.ua/handle/123456789/207540
work_keys_str_mv AT mihailûkva optimalʹnyipribližennyialgoritmreoptimizaciidlâstrogihobobŝennyhzadačovypolnimosti
AT mihailûkva optimalʹniinabliženiialgoritmreoptimízacíídlâstrogihuzagalʹnenihzadačprovikonuvanístʹ
AT mihailûkva optimalapproximationalgorithmforreoptimizationofstrictconstraintsatisfactionproblems