Hamiltonian cycles and Markov chains

Hamiltonian cycles and Markov chains

0.00 Avg rating0 Votes
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: ,
Keywords: programming: dynamic, programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.