p-approximation algorithm

[A'Y]

Как значение этой оценки $\rho$ перевести в проценты? Например, есть приближенный алгоритм с гарантированным приближением $\rho=1,5$ - как перевести это в "этот приближенных алгоритм в худшем случае дает решение, отличающееся от оптимального на столько-то процентов".

-- 21.06.2012, 02:16 --

Вроде $OPT$ меньше или равно $f(x)$ меньше или равно $\rho\, OPT$. Тогда возьмем любое значение $OPT$, например, единицу, и получим неравенство для значения, получающегося в ходе работы нашего приближенного алгоритма: $1$ меньше или равно $f(x)$ меньше или равно $1,5$. То есть на $50%$ в худшем случае отличается решение, даваемое нашим приближенным алгоритмом от оптимального точного решения той же оптимизационной задачи. Верно?