This project involves further investigation in the area of generation of test cases for NP-hard problems. This area has to do with the design of efficient algorithms to produce instances of NP- hard problems with known answers, in such a way that the sets of instances produced are useful for the empirical testing of approximation algorithms for these problems. Previous work consisted of theoretical results concerning the existence of different types of test case generators, and the design of test case construction algorithms for certain NP-hard graph problems. For the proposed research the overall goals are to improve on the generation procedures, to expand their applicability, and to gain more insight into the relationship between the instances generated by the procedures and the problem or application instances. The project will include consideration of construction algorithms for problems in different application areas; and the investigation, through both analytical and empirical means, of the effect of well- known approximation algorithms on sets of generated instances.
