Feasible Bases for a Polytope Related to the Hamilton Cycle Problem
成果类型：
Article
署名作者：
Kalinowski, Thomas; Mohammadian, Sogol
署名单位：
University of New England; University of Newcastle
刊物名称：
MATHEMATICS OF OPERATIONS RESEARCH
ISSN/ISSBN：
0364-765X
DOI：
10.1287/moor.2020.1112
发表日期：
2021
页码：
1366-1389
关键词：
摘要：
We study a certain polytope depending on a graph G and a parameter beta is an element of(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 beta 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.