Proof of the Hamiltonicity-Trace conjecture for singularly perturbed Markov chains

V. Ejov, Nelli Litvak, G. Nguyen

Research output: Book/ReportReportProfessional

79 Downloads (Pure)

Abstract

We prove the conjecture formulated in the paper by N. Litvak and V. Ejov ("Markov Chains and Optimality of The Hamiltonian Cycle", to appear in Math. Oper. Res., 2008), namely, that the trace of the fundamental matrix of a singularly perturbed Markov chain is minimized at policies corresponding to Hamiltonian cycles, over the set of all stochastic policies feasible for a given graph.
Original languageUndefined
Place of PublicationEnschede
PublisherStochastic Operations Research (SOR)
Number of pages10
Publication statusPublished - Jun 2008

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.274/1869
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • IR-64811
  • METIS-251008
  • MSC-11C20
  • MSC-05C45
  • MSC-60J10
  • EWI-12877

Cite this

Ejov, V., Litvak, N., & Nguyen, G. (2008). Proof of the Hamiltonicity-Trace conjecture for singularly perturbed Markov chains. Enschede: Stochastic Operations Research (SOR).