The Estimation of the Individual Travelling Salesman Problem Complexity Extreme Values

P. 261–270.

Zhukova G., Ulyanov M.

This article is about the probability distribution of the maximum of the logarithm of the complexity of an individual travelling salesman problem. The complexity is defined as a number of nodes of the decision tree, which was created by the branch and bound algorithm. We applied our earlier results that the distribution of the logarithm of the complexity of travelling salesman problem can be approximated by the normal distribution. In combination with the representation of the distribution of maximum of normally distributed random variables, we obtain the approximation for the distribution of the maximum of the complexity in cases of infinitely large samples. The accuracy of the approximation was visualized on the graph. In order to simplify the approximation for comparatively small samples, we used the normal distribution with the parameters equal to the expectation and standard deviation of approximation for infinitely large samples. This allowed us to obtain representations for the normal distribution, which approximates the distribution of the maximum of the natural logarithm of the complexity in series of mm travelling salesman problem of size nn. The quality of the representations was analysed by the experiment. On the graph, we showed the quantiles of the theoretical distribution of the maximum of the logarithm of the complexity and the sample’s quantiles in the case of samples of 500 and 1000 travelling salesman problem.

Keywords: complexity, branch and bound method, travelling salesman problem, Largest observation, Sample maximum

In book

Modern Information Technology and IT Education: 12th International Conference, SITITO 2017, Moscow, Russia, November 24–26, 2017, Revised Selected Papers

Vol. 1204. , Springer, 2021.