Оценка качества приближенных алгоритмов

Пусть мы решаем оптимизационную задачу, т. е. ищем объект с наибольшей или наименьшей стоимостью среди множества объектов, на которых задана функция стоимости. Обозначим оптимальное решение как С_опт. А решение, которое дает нам алгоритм как С.

Определение. Приближенный алгоритм решает оптимизационную задачу с ошибкой не более чем в ρ(n) раз, если стоимость оптимального решения С_опт отличается от найденного С не более чем в ρ(n) раз:

max(, ) ≤ ρ(n)≥1.

Заметим, что ρ(n)≥1, так как

1) для задачи максимизации 0<С≤С_опт, следовательно, ≤1,
а ≥1;

2) для задачи минимизации 0<С_опт≤С, следовательно, ≤1,
а ≥1.

Чем ближе к единице оценка ошибки, тем ближе алгоритм к оптимальному.

Здесь и далее под n мы будем понимать длину входа.

Определение. О тносительной ошибкой называется величина, равная (определяется для каждого входа алгоритма).

Определение. Приближенный алгоритм имеет ошибку не более ε(n), если ≤ε(n)≥0 для любого входа длины n.

Замечание. Легко проверить, что ε(n) может быть ограничена сверху через функцию ρ(n), а именно ε(n)≤ρ(n)−1. В самом деле, для задач на минимум это неравенство превращается в равенство. Для задач на максимум ε(n)= (далее нужно вспомнить, что ρ(n)≥1).

Для многих задач известны приближенные алгоритмы, решающие задачу с ошибкой не более чем в некоторое фиксированное число раз (независимо от длины входа). В других случаях такие алгоритмы неизвестны, и приходится довольствоваться алгоритмами, в которых оценка ошибки растет с ростом n.

Для некоторых задач можно улучшать качество приближения (уменьшать относительную ошибку) ценой увеличения времени работы.

Определение. Схемой приближения для данной оптимизационной задачи называется алгоритм, который получает условие задачи и положительное число ε и дает решение с относительной ошибкой не более ε.

Определение. Схема приближения называется полиномиальной, если для любого фиксированного ε>0 время ее работы не превосходит некоторого полинома от n.

Определение. Схема приближения называется полностью полиномиальной, если время её работы ограничено некоторым полиномом от n и от 1⁄ε, где n – размер входа, а ε – оценка относительной ошибки.