Institute of Computer Science
Rheinische Friedrich-Wilhelms-Universität Bonn
4pm Thursday 21st Febraury 2002
Room 2511, JCMB, King's Buildings
We survey some of the recent explicit results on computational complexity of approximating bounded degree, and bounded occurrence combinatorial optimization problems. In particular, we present the best up to now known explicit inapproximability bounds on very small degree optimization problems. Those bounds are of particular importance for proving explicit approximation hardness results for other generic optimization problems, like Traveling Salesman or Minimum Connectivity.