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
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 |
Information:
Date: | Jan. 12, 2006 |
Place: | Niavaran Bldg., Niavaran Square, Tehran, Iran |
|