Article ID: | iaor19941867 |
Country: | United States |
Volume: | 19 |
Issue: | 1 |
Start Page Number: | 223 |
End Page Number: | 237 |
Publication Date: | Feb 1994 |
Journal: | Mathematics of Operations Research |
Authors: | Filar Jerzy A., Krass Dmitry |
Keywords: | programming: dynamic, programming: travelling salesman |
In this paper the authors derive new characterizations of the Hamiltonian cycles of a directed graph, and a new LP-relaxation of the Traveling Salesman Problem. The present results are obtained via an embedding of these combinatorial optimization problems in suitably perturbed controlled Markov chains. This embedding lends probabilistic interpretation to many of the quantities of interest, which in turn lead naturally to the introduction of a quadratic entropy-like function.