| Аннотацiя: | Показано, что для NP-полных задач трудоемким является даже вычисление
шара устойчивости радиуса 1 оптимального решения (т.е при P? NP для этого не
существует полиномиального алгоритма). При использовании жадных алгоритмов для задачи о покрытии множествами (задачи о ранце) при радиусе устойчивости r=O(1) существуют полиноминальные алгоритмы вычисления шара устойчивости радиуса r ln m-приближенного решения (1-приближенного решения).
Ключевые слова: сложность анализа устойчивости. радиус устойчивости задачи, шар устойчивости радиуса r е- приближенного решения задачи.
|