Abstract
For a given NP-hard combinatorial optimization problem, one may identify interesting subclasses of instances with approximation ratios that are better than those that are known for worst case instances. Such a study can serve two purposes. One is to circumvent hardness of approximation results (in cases where they exist). The other is to guide us towards better worst case approximation algorithms (in cases where hardness of approximation results do not exist). The talk will present examples for these two themes.