Алгебраїчний підхід до реоптимізації задач комбінаторної оптимізації та суміжні питання оцінки складності обчислень
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Алгебраїчний підхід до реоптимізації задач комбінаторної оптимізації та суміжні питання оцінки складності обчислень
|
|
| Creator |
Михайлюк, В.О.
|
|
| Description |
Використовується поняття αΛ -наближеного поліморфізму для конструювання ψ(αΛ)-наближеного оптимального алгоритму (ψ(αΛ) = 2-1/αΛ) для реоптимізації CSP задачі MAX - Λ ( Ins - MAX - Λ) з добавленням деякого обмеження. Гіпотеза алгебраїчної дихотомії характеризує NP-складність розглянутого підходу, а базова SDP релаксація для наближених поліморфізмів (BasicSDP) визначає ефективний алгоритм заокруглення для MAX - Λ та Ins - MAX - Λ.
The concept of αΛ -approximation polymorphism is used for design of ψ(αΛ)-approximation optimal algorithm (ψ(αΛ) = 2-1/αΛ) for reoptimization of CSP problem MAX - Λ ( Ins - MAX - Λ) with addition of some constraint. Algebraic dichotomy conjecture characterizes NP - hardness of the considered approach and basic SDP relaxation for approximation polymorphism ( BasicSDP ) defines an efficient rounding algorithm for MAX - Λ and Ins - MAX - Λ. |
|
| Date |
2018-06-10T08:48:16Z
2018-06-10T08:48:16Z 2017 |
|
| Type |
Article
|
|
| Identifier |
Алгебраїчний підхід до реоптимізації задач комбінаторної оптимізації та суміжні питання оцінки складності обчислень / В.О. Михайлюк // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2017. — Вип. 15. — С. 119-125. — Бібліогр.: 6 назв. — укр.
2308-5878 http://dspace.nbuv.gov.ua/handle/123456789/133943 519.854 |
|
| Language |
uk
|
|
| Relation |
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки
|
|
| Publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України
|
|