Separation between Estimation and Approximation
569 views · Published 22 June 2016 · 1:02:28 · Indexed 25 October 2026
Channel: Microsoft Research · 2016 · Science & Technology
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.
