## Separation between Estimation and Approximation

by Uriel Feige and Shlomo Jozeph.

Oddly enough, it seems that this textbook-type result result was not known before. It asserts a separation between the decision and serach version of approximation problems'', akin to the separation that exists for the exact version (for problems that are not NP-complete). The assumption used in the separation is shown to be necessary.
N.B.: The search version is termed an approximation problem, whereas the decision'' version is terms estimation.
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 important special case, we show that there are linear programming relaxations for which no polynomial time rounding technique matches the integrality gap of the linear program.