Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR14-110 | 19th August 2014 16:22

#### Separation between Estimation and Approximation

TR14-110
Authors: Uriel Feige, Shlomo Jozeph
Publication: 21st August 2014 09:10
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.