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
168Kb

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:	Stochastic Operations Research (SOR)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 263887