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||Title of Talk|
|9:00-10:30||Introduction, classical results|
|10:45-12:15||Hardness of approximation, PCP Theorem|
|13:15-14:45||Hardness of Max-3SAT, Vertex Cover, Clique|
|15:00-16:30||Labelcover and hardness of set cover|
Date:|| Jan. 12, 2006|
|Place: ||Niavaran Bldg., Niavaran Square, Tehran, Iran|