Hardness of Approximations
Report ID: TR-504-95Author: Lund, Carsten / Arora, Sanjeev
Date: 1995-12-00
Pages: 54
Download Formats: |Postscript|
Abstract:
Many recent results show that computing approximate solutions to many NP-hard optimization problems is itself NP-hard. This chapter is a self-contained survey of such inapproximability results. It also presents an easy-to-understand framework for proving new inapproxibility results. (to appear as a chapter in the book "Approximation Algorithms for NP-hard problems," editor Dorit Hochbaum)
- This technical report has been published as
- "Hardness of Aproximations," Sanjeev Arora and Carsten Lund in Approximation Algorithms for NP-Hard Problems, edited by Dorit Hochbaum. Published by PWS Publishing, 1997, ISBN/ISSN:0-534-94968-1