Анализ устойчивости задачи о ранце: один отрицательный результат

Abstract

Розглянуто гіпотезу Блера (Blair) про обчислювальну складність задачі, пов язаної з оптимальними розв язками так званих близьких задач про рюкзак. Гіпотезу доведено для узагальнено близьких задач про рюкзак.We consider the Blair hypothesis on the computational complexity of the problem associated with the optimal solutions of the so-called adjacent knapsack problems. The hypothesis is proved for the generalized adjacent knapsack problems.