## Separation between Estimation and Approximation

by Uriel Feige and Shlomo Jozeph.

#### Oded's comments

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.

#### The original abstract

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.

See ECCC TR14-110

Back to
list of Oded's choices.