Analysis of a Random Cut Test Instance Generator for the TSP
Ronald L. Rardin, Craig A. Tovey, Martha G. Pilcher · WORLD SCIENTIFIC eBooks · 1993
Test Instance Generators (TIG’s) are important to evaluate heuristic procedures for NP-hard problems. We analyze a TIG in use for the TSP. This TIG, due to Pilcher and Rardin, is based on a random cut method. We show that it generates a class of instances of intermediate complexity: not as hard as the entire TSP class unless NP = co(NP); not as easy as P unless NP = P. Since the upper bound on complexity must hold for any efficient TIG, our analysis verifies that this random cut TIG is, in a sense, as good as possible a TIG for the TSP. This suggests that the random cut method may be a good basis for constructing TIG’s for other problems. Keywords: traveling salesman problem, complexity, computational test, test case, problem generation 1