Markov chains and optimality of the Hamiltonian cycle

Nelli Litvak, Vladimir Ejov

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

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.
Original languageUndefined
Article number10.1287/moor.1080.0351
Pages (from-to)71-82
Number of pages12
JournalMathematics of operations research
Volume34
Issue number1
DOIs
Publication statusPublished - 27 Jan 2009

Keywords

  • IR-67701
  • METIS-263887
  • MSC-60J10
  • EWI-15437
  • Singular perturbation
  • Hamiltonian cycle
  • Fundamental matrix
  • Markov chains

Cite this

@article{2dac804e9d9d492fb09026aee20c12e9,
title = "Markov chains and optimality of the Hamiltonian cycle",
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.",
keywords = "IR-67701, METIS-263887, MSC-60J10, EWI-15437, Singular perturbation, Hamiltonian cycle, Fundamental matrix, Markov chains",
author = "Nelli Litvak and Vladimir Ejov",
note = "10.1287/moor.1080.0351",
year = "2009",
month = "1",
day = "27",
doi = "10.1287/moor.1080.0351",
language = "Undefined",
volume = "34",
pages = "71--82",
journal = "Mathematics of operations research",
issn = "0364-765X",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "1",

}

Markov chains and optimality of the Hamiltonian cycle. / Litvak, Nelli; Ejov, Vladimir.

In: Mathematics of operations research, Vol. 34, No. 1, 10.1287/moor.1080.0351, 27.01.2009, p. 71-82.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Markov chains and optimality of the Hamiltonian cycle

AU - Litvak, Nelli

AU - Ejov, Vladimir

N1 - 10.1287/moor.1080.0351

PY - 2009/1/27

Y1 - 2009/1/27

N2 - 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.

AB - 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.

KW - IR-67701

KW - METIS-263887

KW - MSC-60J10

KW - EWI-15437

KW - Singular perturbation

KW - Hamiltonian cycle

KW - Fundamental matrix

KW - Markov chains

U2 - 10.1287/moor.1080.0351

DO - 10.1287/moor.1080.0351

M3 - Article

VL - 34

SP - 71

EP - 82

JO - Mathematics of operations research

JF - Mathematics of operations research

SN - 0364-765X

IS - 1

M1 - 10.1287/moor.1080.0351

ER -