Наукова періодика України Кібернетика та системний аналіз

Михайлюк В. А. 
О сложности вычисления параметров устойчивости в задачах булева программирования / В. А. Михайлюк, Н. В. Лищук // Кибернетика и системный анализ. - 2015. - Т. 51, № 5. - С. 56-62. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2015_51_5_7
Показано, что для NP-полных задач трудоемким является даже вычисление шара устойчивости радиуса 1 оптимального решения (т.е. при <$EP~symbol Щ~NP> для этого не существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости r = O(1) существуют полиномиальные алгоритмы вычисления шара устойчивости радиуса r ln m-приближенного решения (1-приближенного решения).
  Повний текст PDF - 97.661 Kb    Зміст випуску     Цитування публікації

Цитованість авторів публікації:
  • Михайлюк В.
  • Лищук Н.

    • Бібліографічний опис для цитування:

    Михайлюк В. А. О сложности вычисления параметров устойчивости в задачах булева программирования / В. А. Михайлюк, Н. В. Лищук // Кибернетика и системный анализ. - 2015. - Т. 51, № 5. - С. 56-62. - Режим доступу: http://nbuv.gov.ua/UJRN/KSA_2015_51_5_7.
      Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
     
    Відділ інформаційно-комунікаційних технологій
    Пам`ятка користувача

    Всі права захищені © Національна бібліотека України імені В. І. Вернадського