Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність
Vernadsky National Library of Ukraine
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність
|
|
| Creator |
Михайлюк, В.О.
|
|
| Subject |
Інформатика та кібернетика
|
|
| Description |
Для розв’язання задачi Ins−Λ−CSP (реоптимiзацiя обмеженої Λ−CSP задачi при додаваннi довiльного обмеження) iснує оптимальний наближений алгоритм з адитивною помилкою з константною складнiстю. Вiдношення апроксимацiї алгоритму залежить вiд цiлочислового розриву лiнiйної релаксацiї вихiдної задачi. Для решения задачи Ins−Λ−CSP (реоптимизация ограниченной Λ−CSP задачи при добавлении произвольного ограничения) существует оптимальный приближенный алгоритм с аддитивной ошибкой с константной сложностью. Отношение аппроксимации алгоритма зависит от целочисленного разрыва линейной релаксации исходной задачи. To solve the problem Ins−Λ−CSP (reoptimization of a bounded-degree Λ−CSP problem under the insertion of an arbitrary constraint), there is an optimal constant-time approximation algorithm with additive error. The approximation ratio of the algorithm depends on the integral gap of a linear relaxation of the initial problem. |
|
| Date |
2015-08-11T13:11:01Z
2015-08-11T13:11:01Z 2013 |
|
| Type |
Article
|
|
| Identifier |
Наближення до оптимальних сублінійних алгоритмів реоптимізації обмежених задач про узагальнену виконуваність / В.О. Михайлюк // Доповiдi Нацiональної академiї наук України. — 2013. — № 4. — С. 38–42. — Бібліогр.: 7 назв. — укр.
1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/85635 519.854 |
|
| Language |
uk
|
|
| Relation |
Доповіді НАН України
|
|
| Publisher |
Видавничий дім "Академперіодика" НАН України
|
|