О сложности вычисления параметров устойчивости в задачах булева программирования / Михайлюк В. А., Лищук Н. В. (2015)
Ukrainian

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

Михайлюк В. А., Лищук Н. В.
О сложности вычисления параметров устойчивости в задачах булева программирования

Показано, что для NP-полных задач трудоемким является даже вычисление шара устойчивости радиуса 1 оптимального решения (т.е. при <$EP~symbol Щ~NP> для этого не существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости r = O(1) существуют полиномиальные алгоритмы вычисления шара устойчивости радиуса r ln m-приближенного решения (1-приближенного решения).

Бібліографічний опис:
Михайлюк В. А., Лищук Н. В. О сложности вычисления параметров устойчивости в задачах булева программирования. Кибернетика и системный анализ. 2015. Т. 51, № 5. С. 56-62. URL: http://jnas.nbuv.gov.ua/article/UJRN-0000412874

English  Cybernetics and Systems Analysis   /     Issue (2015, 51 (5))

translit Transliteration

Mikhajljuk V. A., Lishchuk N. V.
O slozhnosti vychislenija parametrov ustojchivosti v zadachakh buleva programmirovanija

Cite:
Mikhajljuk, V. A., Lishchuk, N. V. (2015). O slozhnosti vychislenija parametrov ustojchivosti v zadachakh buleva programmirovanija. Cybernetics and Systems Analysis, 51 (5), 56-62 http://jnas.nbuv.gov.ua/article/UJRN-0000412874 [In Russian].

 

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

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