Реоптимизация упорядоченных обобщенных задач о выполнимости
При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207498 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Реоптимизация упорядоченных обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 3. — С. 56–65. — Бібліогр.: 16 назв. - рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862590527513296896 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | Реоптимизация упорядоченных обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 3. — С. 56–65. — Бібліогр.: 16 назв. - рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’язання задачі OCSP.
Assume that Unique Games Conjecture (UGC) holds. Then for solving Ins-OCSP (reoptimization of OCSP under insertion of one constraint) polynomial optimal (threshold) approximated algorithm exists. The approximation ratio of this algorithm depends on threshold «random» approximation ratio for solving OCSP problem.
|
| first_indexed | 2025-11-27T05:13:09Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-207498 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-11-27T05:13:09Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2025-10-08T15:04:49Z 2012 Реоптимизация упорядоченных обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2012. — № 3. — С. 56–65. — Бібліогр.: 16 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207498 519.854 10.1615/JAutomatInfScien.v44.i6.60 При істинності унікальної ігрової гіпотези (UGC) для розв’язання задачі InsOCSP (реоптимізація OCSP при додаванні одного обмеження) існує поліноміальний оптимальний (пороговий) наближений алгоритм. Його апроксимаційне відношення залежить від порогового «випадкового» відношення апроксимації для розв’язання задачі OCSP. Assume that Unique Games Conjecture (UGC) holds. Then for solving Ins-OCSP (reoptimization of OCSP under insertion of one constraint) polynomial optimal (threshold) approximated algorithm exists. The approximation ratio of this algorithm depends on threshold «random» approximation ratio for solving OCSP problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Реоптимизация упорядоченных обобщенных задач о выполнимости Реоптимізація впорядкованих узагальнених задач про виконуваність Reoptimization of Ordered Generalized Satisfaction Problems Article published earlier |
| spellingShingle | Реоптимизация упорядоченных обобщенных задач о выполнимости Михайлюк, В.А. Оптимальное управление и методы оптимизации |
| title | Реоптимизация упорядоченных обобщенных задач о выполнимости |
| title_alt | Реоптимізація впорядкованих узагальнених задач про виконуваність Reoptimization of Ordered Generalized Satisfaction Problems |
| title_full | Реоптимизация упорядоченных обобщенных задач о выполнимости |
| title_fullStr | Реоптимизация упорядоченных обобщенных задач о выполнимости |
| title_full_unstemmed | Реоптимизация упорядоченных обобщенных задач о выполнимости |
| title_short | Реоптимизация упорядоченных обобщенных задач о выполнимости |
| title_sort | реоптимизация упорядоченных обобщенных задач о выполнимости |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207498 |
| work_keys_str_mv | AT mihailûkva reoptimizaciâuporâdočennyhobobŝennyhzadačovypolnimosti AT mihailûkva reoptimízacíâvporâdkovanihuzagalʹnenihzadačprovikonuvanístʹ AT mihailûkva reoptimizationoforderedgeneralizedsatisfactionproblems |