Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Contents
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.854
Mikhailyuk V.A., Lishchuk N.V.

THE COMPLEXITY OF CALCULATING SENSITIVITY PARAMETERS IN BOOLEAN PROGRAMMING PROBLEMS

Abstract. The authors show that even calculating the stability ball of radius 1 of the optimal solution is cumbersome for NP -hard problems (i.e., a polynomial algorithm does not exist unless PNP). When greedy algorithms are used for set covering problem (knapsack problem) for stability radius r = O (1), polynomial algorithms of calculating the stability ball of radius r of ln m -approximate solution (1-аpproximate solution) exist.

Keywords: complexity of sensitivity analysis, stability radius of a problem, stability ball of radius r for an ε -approximate problem solution.



FULL TEXT

Михайлюк Виктор Алексеевич,
доктор физ.-мат. наук, доцент Восточноевропейского национального университета имени Леси Украинки, Луцк, e-mail: mikhailyukvictor2@gmail.com.

Лищук Наталия Викторовна,
аспирантка Восточноевропейского национального университета имени Леси Украинки, Луцк,
e-mail: lnatalkav@mail.ru.

© 2016 Kibernetika.org. All rights reserved.