Abstract

Most interesting optimization problems are NP-hard, meaning it is impossible to compute exact solutions to these problems in polynomial time unless P = NP. In many situations, finding a solution efficiently that is provably close to an optimal one is also acceptable. This leads to study of approximation algorithms. An algorithm with approximation ratio C computes, for every problem instance, a solution whose cost is within a factor C of the optimum solution. In this short tutorial we present some results about finding provably good approximation solutions for some classical NP-hard optimization problems. Then we focus on proving lower bounds, i.e. showing hardness of approximation for these problems. This starts with giving a new characterization of NP in terms of Probabilistic Checkable Proof systems and the PCP Theorem. Then we show how this theorem can be used to prove inapproximability results.



Time Table