Лекция 10: Применение теории NP-полноты к разработке приближенных алгоритмов

Подробности

Категория: Алгоритмы и модели вычислений

Невозможность существования полиномиального приближенного алгоритма с фиксированной погрешностью для некоторых NP-трудных задач. Приближенный полиномиальный алгоритм решения задачи коммивояжера с неравенством треугольника.