Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-110 | 19th August 2014 16:22

Separation between Estimation and Approximation

RSS-Feed




TR14-110
Authors: Uriel Feige, Shlomo Jozeph
Publication: 21st August 2014 09:10
Downloads: 3793
Keywords: 


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.



ISSN 1433-8092 | Imprint