\input zb-basic
\input zb-ioport
\iteman{io-port 02228328}
\itemau{Ejov, Vladimir; Filar, Jerzy A.; Nguyen, Minh-Tuan}
\itemti{Hamiltonian cycles and singularly perturbed Markov chains.}
\itemso{Math. Oper. Res. 29, No. 1, 114-131 (2004).}
\itemab
Summary: 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, $\varepsilon$, is less than or equal to $1/N^2$, 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.
\itemrv{~}
\itemcc{}
\itemut{Markov decision process; optimal policy; singular perturbation}
\itemli{doi:10.1287/moor.1030.0066}
\end