Оптимальный приближенный алгоритм реоптимизации для строгих обобщенных задач о выполнимости
При виконанні унікальної ігрової гіпотези (UGC) для реоптимізації строгих узагальнених задач про виконуваність (при включенні довільного обмеження) існує оптимальний наближений алгоритм. Відношення апроксимації цього алгоритму залежить від цілочисельного розриву лінійної релаксації вихідної задачі....
Gespeichert in:
| 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 |