К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации / Михайлюк В. А. (2011)
Ukrainian

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0000029873
  Кибернетика и системный анализ      А - 2019  /     Випуск (2011, Т. 47, № 3)

Михайлюк В. А.
К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации

Показано, що для реоптимізації задачі про покриття множинами у разі вставлення або звільнення елемента в довільну множину не існує поліноміально наближеної схеми. Подібний результат має місце для задачі "мінімальне розфарбування графа" у разі вставлення довільної вершини не більше ніж з двома інцидентними їй ребрами і задачі "мінімальне пакування в контейнери" за умов звільнення довільного предмета.

Бібліографічний опис:
Михайлюк В. А.  К вопросу о существовании полиномиально приближенных схем для реоптимизации дискретных задач оптимизации. Кибернетика и системный анализ. 2011. Т. 47, № 3. С. 42-50. URL: http://jnas.nbuv.gov.ua/article/UJRN-0000029873

English  Cybernetics and Systems Analysis   /     Issue (2011, 47 (3))

translit Transliteration

Mikhajljuk V. A.
K voprosu o sushchestvovanii polinomialno priblizhennykh skhem dlja reoptimizatsii diskretnykh zadach optimizatsii

Cite:
Mikhajljuk, V. A. (2011). K voprosu o sushchestvovanii polinomialno priblizhennykh skhem dlja reoptimizatsii diskretnykh zadach optimizatsii. Cybernetics and Systems Analysis, 47 (3), 42-50 http://jnas.nbuv.gov.ua/article/UJRN-0000029873 [In Russian].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна