Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами
|
|
| Creator |
Михайлюк, В.А.
Сергиенко, И.В. |
|
| Subject |
Кибернетика
|
|
| Description |
Якщо k=O(logn) і предикат P спадково апроксимаційно-стійкий для реоптимізації проблеми Max-EkCSP-P, при вставці нового істинісного значення в предикат і деякого обмеження існує поліноміальний наближений алгоритм з відношенням апроксимації, яке є пороговим.
If k=O(logn) and a predicate Р is approximation resistant for the reoptimization of problem Max-EkCSP-P under insertion of a truth-value in the predicate and some constraint, then there exists a polynomial algorithm with the approximation ratio that is threshold |
|
| Date |
2015-07-02T08:13:39Z
2015-07-02T08:13:39Z 2012 |
|
| Type |
Article
|
|
| Identifier |
Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами / В.А. Михайлюк, И.В. Сергиенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 89-104. — Бібліогр.: 23 назв. — рос.
0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/84019 519.854 |
|
| Language |
ru
|
|
| Relation |
Кибернетика и системный анализ
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|