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 P ≠ NP). 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.
Михайлюк Виктор Алексеевич,
доктор физ.-мат. наук, доцент Восточноевропейского национального университета имени Леси Украинки, Луцк,
e-mail: mikhailyukvictor2@gmail.com.
Лищук Наталия Викторовна,
аспирантка Восточноевропейского национального университета имени Леси Украинки, Луцк,
e-mail: lnatalkav@mail.ru.