Feasible bases for a polytope related to the Hamilton cycle problem

07/30/2019
by   Thomas Kalinowski, et al.
0

We study a certain polytope depending on a graph G and a parameter β∈(0,1) which arises from embedding the Hamiltonian cycle problem in a discounted Markov decision process. Eshragh et al. conjectured a lower bound on the proportion of feasible bases corresponding to Hamiltonian cycles in the set of all feasible bases. We make progress towards 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 1, (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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset