首页    期刊浏览 2024年09月12日 星期四
登录注册

文章基本信息

  • 标题:Separation between Estimation and Approximation
  • 本地全文:下载
  • 作者:Uriel Feige ; Shlomo Jozeph
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    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 , but it is difficult to find a solution whose value is within 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.

国家哲学社会科学文献中心版权所有