Hardness of Approximations

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