Hamiltonian cycles and singularly perturbed Markov chains

Hamiltonian cycles and singularly perturbed Markov chains

0.00 Avg rating0 Votes
Article ID: iaor20072031
Country: United States
Volume: 29
Issue: 1
Start Page Number: 114
End Page Number: 131
Publication Date: Feb 2004
Journal: Mathematics of Operations Research
Authors: , ,
Abstract:

We consider the Hamiltonian cycle problem embedded in a singularly perturbed Markov decision process. We also consider a functional on the space of deterministic policies of the process that consists of the (1,1)-entry of the fundamental matrices of the Markov chains induced by the same policies. We show that when the perturbation parameter, ϵ, is less than or equal to 1/N2, the Hamiltonian cycles of the directed graph are precisely the minimizers of our functional over the space of deterministic policies. In the process, we derive analytical expressions for the possible N distinct values of the functional over the, typically, much larger space of deterministic policies.

Reviews

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