We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Hamiltonian Cycles and Singularly Perturbed Markov Chains.
- Authors
Ejov, Vladimir; Filar, Jerzy A.; Nguyen, Minh-Tuan
- 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.
- Subjects
HAMILTONIAN systems; MARKOV processes; PERTURBATION theory; STOCHASTIC processes; OPERATIONS research
- Publication
Mathematics of Operations Research, 2004, Vol 29, Issue 1, p114
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.1030.0066