Feasible Bases for a Polytope Related to the Hamilton Cycle Problem

Thomas Kalinowski () and Sogol Mohammadian ()
Additional contact information
Thomas Kalinowski: Department of Mathematics, School of Science and Technology, University of New England, Armidale, New South Wales 2350, Australia
Sogol Mohammadian: Department of Mathematics, School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, New South Wales 2308, Australia

Mathematics of Operations Research, 2021, vol. 46, issue 4, 1366-1389

Abstract: We study a certain polytope depending on a graph G and a parameter β ∈ (0,1) that arises from embedding the Hamiltonian cycle problem in a discounted Markov decision process. Literature suggests a conjecture a lower bound on the proportion of feasible bases corresponding to Hamiltonian cycles in the set of all feasible bases. We make progress toward a proof of the conjecture by proving results about the structure of feasible bases. In particular, we prove three main results: (1) the set of feasible bases is independent of the parameter β when the parameter is close to one, (2) the polytope can be interpreted as a generalized network flow polytope, and (3) we deduce a combinatorial interpretation of the feasible bases. We also provide a full characterization for a special class of feasible bases, and we apply this to provide some computational support for the conjecture.

Keywords: Primary: 90C40; 90C35; secondary: 05C80; 05C81; Primary: Networks/graphs; secondary: probability; random walk; Hamilton cycle; polytope; feasible basis; random walk (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2020.1112 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:4:p:1366-1389

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().