- Title
- Hamiltonian cycles and subsets of discounted occupational measures
- Creator
- Eshragh, Ali; Filar, Jerzy A.; Kalinowski, Thomas; Mohammadian, Sogol
- Relation
- Mathematics of Operations Research Vol. 45, Issue 2, p. 713-731
- Publisher Link
- http://dx.doi.org/10.1287/moor.2019.1009
- Publisher
- Institute for Operations Research and the Management Sciences (INFORMS)
- Resource Type
- journal article
- Date
- 2020
- Description
- We study a certain polytope arising from embedding the Hamiltonian cycle problem in a discounted Markov decision process. The Hamiltonian cycle problem can be reduced to finding particular extreme points of a certain polytope associated with the input graph. This polytope is a subset of the space of discounted occupational measures. We characterize the feasible bases of the polytope for a general input graph G and determine the expected numbers of different types of feasible bases when the underlying graph is random. We utilize these results to demonstrate that augmenting certain additional constraints to reduce the polyhedral domain can eliminate a large number of feasible bases that do not correspond to Hamiltonian cycles. Finally, we develop a random walk algorithm on the feasible bases of the reduced polytope and present some numerical results. We conclude with a conjecture on the feasible bases of the reduced polytope.
- Subject
- Hamiltonian cycle; discounted occupational measures; feasible basis; random graph; random walk
- Identifier
- http://hdl.handle.net/1959.13/1418444
- Identifier
- uon:37349
- Identifier
- ISSN:0364-765X
- Language
- eng
- Full Text
- Reviewed
- Hits: 3445
- Visitors: 2529
- Downloads: 267
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 363 KB | Adobe Acrobat PDF | View Details Download |