THE ESTIMATIONS OF THE PARAMETERS OF THE DISTRIBUTION OF THE NATURAL LOGARITHM OF THE COMPLEXITY OF TSP
Abstract
The complexity of the individual travelling salesman problem was analyzed by means of mathematical statistics. The complexity is defined as a number of nodes of the decision tree, which was created by the branch and bound algorithm. We obtained approximate representations for parameters of probability distribution of the natural logarithm of the complexity. These representations are functions of the dimension of the problem. The linear function is used to construct the upper estimation for the quantiles of the natural logarithm of the complexity, in cases when the level of the quantile is more than 0.5. We also apply this formula for the lower bound of the quantiles of levels less than 0.5. Then we use the normal distribution as an approximation of the distribution of the natural logarithm of the complexity. We combine a nonlinear function for a scale parameter and linear function for a location parameter and obtain a lower bound for the quantiles of the level 0.95 of the natural logarithm of the complexity. The quality of the estimations was analyzed by the experiment. In our experiment the sample’s quantiles of the level 0.95 differ from the estimation less than 0.3% in the case of the dimension of the problem in range from 45 to 50.
References
2. Dantzig G. B., Fulkerson R., Johnson S. Solution of a large scale traveling salesman problem. Technical Report P-510. RAND Corporation, Santa Monica, California, USA. – 1954.
3. Dantzig, G. B., Fulkerson D. R., Johnson S. M. «On a linearprogramming, combinatorial approach to the traveling-salesman problem» // Operations Research 1959. №7, pp. 58–66.
4. Eastman, W. L. Linear Programming with Pattern Constraints. Ph.D. Thesis. Department of Economics, Harvard University, Cambridge, Massachusetts, USA. – 1958.
5. Land, A. H., Doig A. G. «An automatic method of solving discrete programming problems» // Econometrica 1960. №28, pp. 497–520.
6. Little, J. D. C., Murty K. G., Sweeney D.W., Karel C. «An algorithm for the traveling salesman problem» // Operations Research, 1963. №11, pp. 972–989.
7. Ul'janov M.V. Resursno-jeffektivnye komp'juternye algoritmy. Razrabotka i analiz. — M.: FIZMATLIT, 2008. — 304 s.
8. Ul'janov M.V., Fomichev M.I. «Resursnye harakteristiki sposobov organizacii dereva reshenij v metode vetvej i granic dlja zadachi kommivojazhera» // Biznes – informatika, 2015. № 4 (34). S. 38–46.
9. Moors J. J. A. A quantile alternative for kurtosis// The Statistician, 1988. Vol. 37, pp. 25–32.
10. Moors J. J. A., Coenen V. M. J., Heuts R. M. J. «Limiting distributions of moment- and quantile-based measures for skewness and kurtosis». School of Economics and Management, Tilburg University, Res. Mem. FEW 620, 1993.
11. Moors J. J. A., Wagemakers R. Th. A., Coenen V. M. J., Heuts R. M. J., Janssens M. J. B. T. «Characterizing systems of distributions by quantile measures» // Statistica Neerlandica, 1996. Vol. 50, № 3, pp. 417–430.
12. Jonhnson N.L., Kotz S., and Balakrishnan N. Continuous Univariate Distributions. Vol. 2, Wiley, 1995.
13. Goloveshkin V.A., Zhukova G.N., Ul'janov M.V., Fomichjov M.I. Ispol'zovanie kvantil'nyh kojefficientov asimmetrii i jekscessa dlja ocenki slozhnosti reshenija zadachi kommivojazhera. International Journal of Open Information Technologies. 2016. T. 4. № 12. S. 7-12.
14. Kramer G. Matematicheskie metody statistiki. — M.: Mir, 1975. — 648 s.
15. Pearson, K. «Contributions to the Mathematical Theory of Evolution. III. Regression, Heredity and Panmixia» // Philosophical Transactions of the Royal Society of London, 1896. 187, pp. 253–318.
16. Goloveshkin V.A., Zhukova G.N., Ul'janov M.V., Fomichev M.I. «Sravnenie resursnyh harakteristik tradicionnogo i modificirovannogo metoda vetvej i granic dlja TSP» // Sovremennye informacionnye tehnologii i IT-obrazovanie, 2015. T. 2, № 11. S. 151-159.
17. Goloveshkin V.A., Zhukova G.N., Ul'janov M.V., Fomichjov M.I. Ob odnom obobshhjonnom predstavlenii klassov individual'nyh zadach kommivojazhjora// Avtomatizacija. Sovremennye tehnologii. 2016. № 10. S. 22-29.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
