Markov chains, Hamiltonian cycles and volumes of convex bodies

Vivek Borkar, Jerzy Filar

    Research output: Contribution to journalArticle

    2 Citations (Scopus)

    Abstract

    In this note the Hamiltonian cycle problem is mapped into an infinite horizon discounted cost constrained Markov decision problem. The occupation measure based linear polytope associated with this control problem defines a convex set which either strictly contains or is equal to another convex set, depending on whether the underlying graph has a Hamiltonian cycle or not. This allows us to distinguish Hamiltonian graphs from non-Hamiltonian graphs by comparing volumes of two convex sets.

    Original languageEnglish
    Pages (from-to)633-639
    Number of pages7
    JournalJournal of Global Optimization
    Volume55
    Issue number3
    DOIs
    Publication statusE-pub ahead of print - 2013

    Fingerprint Dive into the research topics of 'Markov chains, Hamiltonian cycles and volumes of convex bodies'. Together they form a unique fingerprint.

  • Cite this