All reports by Author Shlomo Jozeph:

__
TR14-110
| 19th August 2014
__

Uriel Feige, Shlomo Jozeph#### Separation between Estimation and Approximation

Uriel Feige, Shlomo Jozeph

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.

As an ...
more >>>