A Computational Approach to TSP Performance Prediction Using Data Mining

The increase in the use of parallel distributed architectures in order to solve large-scale scientific problems has generated the need for performance prediction for both deterministic applications and non-deterministic applications. The development of a new prediction methodology to estimate the execution time of a hard data-dependent parallel application that solves the traveling salesman problem (TSP) is the primary target of this study. It consists of two big stages: the execution of the TSP algorithms with different input data in order to collect useful data and the application of a data mining procedure through a KDD process. The approach makes it also possible to evaluate other practical problems that can be formulated as TSP problems. The experimental results are quite promising, the capacity of prediction is greater than 75%.