О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости
Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі. For solving Ins-Λ-C...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/207602 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862696864203145216 |
|---|---|
| author | Михайлюк, В.А. |
| author_facet | Михайлюк, В.А. |
| citation_txt | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі.
For solving Ins-Λ-CSP (reoptimization of Λ-CSP under insertion of one constraint) an optimal approximation algorithm with additive error exists. Approximation ratio of this algorithm depends on the integrality gap of LP relaxation of the initial problem.
|
| first_indexed | 2025-12-07T16:28:11Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-207602 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T16:28:11Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. 2025-10-10T10:41:32Z 2013 О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости / В.А. Михайлюк // Проблемы управления и информатики. — 2013. — № 2. — С. 78–86. — Бібліогр.: 12 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207602 519.854 10.1615/JAutomatInfScien.v45.i4.40 Для розв’язання задачі Ins-Λ-CSP (реоптимізація Λ-CSP при додаванні одного обмеження) існує оптимальний наближений алгоритм з адитивною помилкою з константною складністю. При цьому відношення апроксимації алгоритму залежить від цілочислового розриву LP-релаксації вихідної задачі. For solving Ins-Λ-CSP (reoptimization of Λ-CSP under insertion of one constraint) an optimal approximation algorithm with additive error exists. Approximation ratio of this algorithm depends on the integrality gap of LP relaxation of the initial problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости Про сублінійні алгоритми реоптимізації для узагальнених задач про виконуваність On Sublinear Algorithms of Reoptimization for Generalized Satisfiability Problems Article published earlier |
| spellingShingle | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости Михайлюк, В.А. Оптимальное управление и методы оптимизации |
| title | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_alt | Про сублінійні алгоритми реоптимізації для узагальнених задач про виконуваність On Sublinear Algorithms of Reoptimization for Generalized Satisfiability Problems |
| title_full | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_fullStr | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_full_unstemmed | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_short | О сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| title_sort | о сублинейных алгоритмах реоптимизации для обобщенных задач о выполнимости |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207602 |
| work_keys_str_mv | AT mihailûkva osublineinyhalgoritmahreoptimizaciidlâobobŝennyhzadačovypolnimosti AT mihailûkva prosublíníiníalgoritmireoptimízacíídlâuzagalʹnenihzadačprovikonuvanístʹ AT mihailûkva onsublinearalgorithmsofreoptimizationforgeneralizedsatisfiabilityproblems |