Separation between Estimation and Approximation

Опубликовано 22 июня 2016, 1:15

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 r, but it is difficult to find a solution whose value is within r 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. Joint work with Shlomo Jozeph.