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.