Publicações > Artigos ou Capítulos em Livros Editados

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

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.