2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

-- 21.06.2012, 02:16 --

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

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group