Probabilistic Prediction of the Complexity of Traveling Salesman Problems Based on Approximating the Complexity Distribution from Experimental Data


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

We show the results of a statistical study of the complexity of the asymmetric traveling salesman problem (ATSP) obtained by processing a specially generated pool of matrices. We show that the normal distribution can serve as an approximation to the distribution of the logarithm of complexity for a fixed problem dimension. We construct a family of probability distributions that represent satisfactory approximations of the complexity distribution with a dimension of the cost matrix from 20 to 49. Our main objective is to make probabilistic predictions of the complexity of individual problems for larger values of the dimension of the cost matrix. We propose a representation of the complexity distribution that makes it possible to predict the complexity. We formulate the unification hypothesis and show directions for further study, in particular proposals on the task of clustering “complex” and “simple” ATSP problems and proposals on the task of directly predicting the complexity of a specific problem instance based on the initial cost matrix.

About the authors

V. A. Goloveshkin

Moscow Technological University; Institute of Applied Mechanics

Author for correspondence.
Email: nikshevolog@yandex.ru
Russian Federation, Moscow; Moscow

G. N. Zhukova

National Research University Higher School of Economics

Email: nikshevolog@yandex.ru
Russian Federation, Moscow

M. V. Ulyanov

Institute of Control Sciences; Lomonosov State University

Email: nikshevolog@yandex.ru
Russian Federation, Moscow; Moscow

M. I. Fomichev

National Research University Higher School of Economics

Email: nikshevolog@yandex.ru
Russian Federation, Moscow

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2018 Pleiades Publishing, Ltd.