The estimation of the complexity of solving a particular travelling salesman problem by quantile-based measures for skewness and kurtosis

V. A. Goloveshkin, G.N. Zhukova, M.V. Ulyanov, M.I. Fomichev

Abstract


The complexity of solving a particular travelling saleman problem is studied. Complexity is a number of nodes of the decision tree, when a particular problem is being solved by the branch and bound algorithm. A probability distribution of the logarithm of the complexity of a particular TSP is approximately normal. Parameters of the linear transformation of a sample of the logarithm of the complexity into a standard normally distributed sample are obtained by the method of least squares for the sample quantiles. The formulas for the parameters are also given.

Full Text:

PDF (Russian)

References


J. D. C. Little, K. G. Murty, D.W. Sweeney, and C. Karel, “An algorithm for the traveling salesman problem,” Operations Research, vol. 11, pp. 972–989, 1963.

G. B. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a large scale traveling salesman problem,” RAND Corp., Santa Monica, CA, Tech. Rep. P-510, 1954.

G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, “On a linear programming, combinatorial approach to the traveling-salesman problem,” Operations Research, vol. 7, pp. 58–66, 1959.

W. L. Eastman, “Linear Programming with Pattern Constraints,” Ph.D. thesis, Dept. Economics, Harvard Univ., Cambridge, MA, 1958.

A. H. Land and A. G. Doig, “An automatic method of solving discrete programming problems,” Econometrica, vol. 28, pp. 497–520, 1960.

A. S. Manne and H. M. Markowitz, “On the solution of discrete programming problems,” RAND Corp., Santa Monica, CA, Tech. Rep. P-711, 1956.

C. Cotta, J. Aldana, A. Nebro, and J. Troya, “Hybridizing genetic algorithms with branch and bound techniques for the resolution of the TSP”, in Artificial Neural Nets and Genetic Algorithms, D. Pearson, N. Steele, R. Albrecht, Eds. Wien New York: Springer–Verlag, 1995, pp. 277-280.

G. Carpaneto and P. Toth, “Some new branching and bounding criteria for the asymmetric traveling salesman problem,” Management Science, vol. 26, 1980, pp. 736–743.

D. E. Knuth, “Estimating the efficiency of backtracking programs,” Mathematics of Computing, vol. 29, 1975, pp. 121–136.

G. Cornuéjols, M. Karamanov, and Y. Li, “Early estimates of the size of branch-and-bound trees,” INFORMS J. Comp., vol. 18, No. 1, 2006, pp. 86–96.

G. Kramer, “Matematicheskie metody statistiki”, M.: Mir, 1975, 648 s.

N.L. Jonhnson, S. Kotz, and N. Balakrishnan, “Continuous Univariate Distributions,” vol. 2, Wiley, 1995.

K. Pearson, “Contributions to the Mathematical Theory of Evolution. III. Regression, Heredity and Panmixia,” Phil. Trans. Royal Soc. London, vol. 187, 1896, pp. 253–318.

J. J. A. Moors, “A quantile alternative for kurtosis,” The Statistician, vol. 37, 1988, pp. 25–32.

J. J. A. Moors, V. M. J. Coenen, and R. M. J. Heuts, “Limiting distributions of moment- and quantile-based measures for skewness and kurtosis”, School of Economics and Management, Tilburg University, Res. Mem. FEW 620, 1993

J. J. A. Moors, R. Th. A. Wagemakers, V. M. J. Coenen, R. M. J. Heuts, and M. J. B. T. Janssens, “Characterizing systems of distributions by quantile measures”, Statistica Neerlandica, vol. 50, No 3, pp. 417–430, Nov. 1996.

M.V. Ul'janov, M.I. Fomichev, “Resursnye harakteristiki sposobov organizacii dereva reshenij v metode vetvej i granic dlja zadachi kommivojazhera”, Biznes – informatika, #4, 2015.

M.V. Ul'janov, “Resursno-jeffektivnye komp'juternye algoritmy. Razrabotka i analiz.” M.: FIZMATLIT, 2008. 304 s.

V.A. Goloveshkin, G.N. Zhukova, M.V. Ul'janov, M.I. Fomichev “Sravnenie resursnyh harakteristik tradicionnogo i modificirovannogo metoda vetvej i granic dlja TSP,” Sovremennye informacionnye tehnologii i IT-obrazovanie, T. 2, # 11, 2015, 614 s.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162