- Title
- Feasible bases for a polytope related to the Hamilton cycle problem
- Creator
- Kalinowski, Thomas; Mohammadian, Sogol
- Relation
- Mathematics of Operations Research Vol. 46, Issue 4, p. 1366-1389
- Publisher Link
- http://dx.doi.org/10.1287/moor.2020.1112
- Publisher
- Institute for Operations Research and the Management Sciences (INFORMS)
- Resource Type
- journal article
- Date
- 2021
- Description
- 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.
- Subject
- Hamilton cycle; polytope; feasible basis; random walk
- Identifier
- http://hdl.handle.net/1959.13/1439561
- Identifier
- uon:40962
- Identifier
- ISSN:0364-765X
- Language
- eng
- Reviewed
- Hits: 3897
- Visitors: 747
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|