Abstract
Most interesting optimization problems are NPhard, 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 NPhard 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
Time  Title of Talk 
9:0010:30  Introduction, classical results 
10:4512:15  Hardness of approximation, PCP Theorem 
13:1514:45  Hardness of Max3SAT, Vertex Cover, Clique 
15:0016:30  Labelcover and hardness of set cover 
Information:
Date:  Jan. 12, 2006 
Place:  Niavaran Bldg., Niavaran Square, Tehran, Iran 
