# Markov chains and optimality of the Hamiltonian cycle

Litvak, Nelly
and
Ejov, Vladimir
(2009)
*Markov chains and optimality of the Hamiltonian cycle.*
Mathematics of operations research, 34
(1).
pp. 71-82.
ISSN 0364-765X

PDF
Restricted to UT campus only : Request a copy 172kB |

Abstract: | We consider the Hamiltonian cycle problem (HCP) embedded in a controlled Markov decision process. In this setting, HCP reduces to an optimization problem on a set of Markov chains corresponding to a given graph. We prove that Hamiltonian cycles are minimizers for the trace of the fundamental matrix on a set of all stochastic transition matrices. In case of doubly stochastic matrices with symmetric linear perturbation, we show that Hamiltonian cycles minimize a diagonal element of a fundamental matrix for all admissible values of the perturbation parameter. In contrast to the previous work on this topic, our arguments are primarily based on probabilistic rather than algebraic methods. |

Item Type: | Article |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/67701 |

Official URL: | http://dx.doi.org/10.1287/moor.1080.0351 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 263887