Markov chains and optimality of the Hamiltonian cycle
Date
2009
Authors
Litvak, N.
Ejov, V.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Mathematics of Operations Research, 2009; 34(1):71-82
Statement of Responsibility
Conference Name
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.
School/Discipline
Dissertation Note
Provenance
Description
Link to a related website: https://ris.utwente.nl/ws/files/5103928/memo1841.pdf, Open Access via Unpaywall
Access Status
Rights
Copyright 2009 INFORMS