Markov chains and optimality of the Hamiltonian cycle

Nelli Litvak, Vladimir Ejov

Research output: Book/ReportReportProfessional

101 Downloads (Pure)

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
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages12
Publication statusPublished - Jun 2007

Publication series

NameMemorandum
PublisherUniversity of Twente, Department of Applied Mathematics
No.06472/1841
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • EWI-10244
  • MSC-05C45
  • Singular perturbation
  • Hamiltonian cycle
  • Fundamental matrix
  • MSC-60J10
  • Markov chains
  • IR-64109
  • MSC-15A51
  • METIS-241665

Cite this

Litvak, N., & Ejov, V. (2007). Markov chains and optimality of the Hamiltonian cycle. (Memorandum; No. 06472/1841). Enschede: University of Twente, Department of Applied Mathematics.
Litvak, Nelli ; Ejov, Vladimir. / Markov chains and optimality of the Hamiltonian cycle. Enschede : University of Twente, Department of Applied Mathematics, 2007. 12 p. (Memorandum; 06472/1841).
@book{6606469d33144e6090c1218eaa100b3e,
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 = "EWI-10244, MSC-05C45, Singular perturbation, Hamiltonian cycle, Fundamental matrix, MSC-60J10, Markov chains, IR-64109, MSC-15A51, METIS-241665",
author = "Nelli Litvak and Vladimir Ejov",
year = "2007",
month = "6",
language = "Undefined",
series = "Memorandum",
publisher = "University of Twente, Department of Applied Mathematics",
number = "06472/1841",

}

Litvak, N & Ejov, V 2007, Markov chains and optimality of the Hamiltonian cycle. Memorandum, no. 06472/1841, University of Twente, Department of Applied Mathematics, Enschede.

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

Enschede : University of Twente, Department of Applied Mathematics, 2007. 12 p. (Memorandum; No. 06472/1841).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Markov chains and optimality of the Hamiltonian cycle

AU - Litvak, Nelli

AU - Ejov, Vladimir

PY - 2007/6

Y1 - 2007/6

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 - EWI-10244

KW - MSC-05C45

KW - Singular perturbation

KW - Hamiltonian cycle

KW - Fundamental matrix

KW - MSC-60J10

KW - Markov chains

KW - IR-64109

KW - MSC-15A51

KW - METIS-241665

M3 - Report

T3 - Memorandum

BT - Markov chains and optimality of the Hamiltonian cycle

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Litvak N, Ejov V. Markov chains and optimality of the Hamiltonian cycle. Enschede: University of Twente, Department of Applied Mathematics, 2007. 12 p. (Memorandum; 06472/1841).