The Traveling Salesman Problem and the Gnedenko theorem
Salvador, T.; Morais, M. C.
New Advances in Statistical Modeling and Applications, Studies in Theoretical and Applied Statistics, Springer-Verlag (2014), 197-206
http://dx.doi.org/10.1007/978-3-319-05323-3_19
The traveling salesman problem (TSP) has three characteristics common to most problems, which have attracted and intrigued mathematicians: the simplicity of its definition, the wealth of its applications, and the inability to find its optimal solution in polynomial-time.In this paper, we provide point and interval estimates for the optimal cost of several instances of the TSP, by using the solutions obtained by running four approximate algorithms—the 2-optimal and 3-optimal algorithms and their greedy versions—and considering the three-parameter Weibull model, whose location parameter represents the (unknown) optimal cost of the TSP.
|
