HARDNESS OF APPROXIMATION

Most optimization problems arising in an important application area to solve real world problems are NP-hard.  Due to the widely accepted belief that P ≠ NP, it is time consuming to find exact solutions for these problems.  Therefore, approximation algorithms have been implemented for the problems which solve them efficiently but not exactly.  However, finding some approximation results is as hard as finding exact results.  Computational Complexity Theory for the field of hardness of approximation states a limit of approximation results.  A Probabilistically Checkable Proof (PCP) is a type of proof that can be checked by a randomized verification algorithm with bounded query complexity.  With the development of “PCP Theorem” which states that PCP(log n, 1) = NP, many inapproximability results have been established.  This paper will review results of hardness of approximation proved in the last decade.