Markov chains, Hamiltonian cycles and volumes of convex bodies

Vivek Borkar, Jerzy Filar

    Research output: Contribution to journalArticlepeer-review

    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
    Early online date2013
    DOIs
    Publication statusPublished - Mar 2013

    Keywords

    • Discounted cost
    • Hamiltonian cycle problem
    • Markov decision process
    • Uniform sampling
    • Volumes of convex sets

    Fingerprint

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

    Cite this