Please use this identifier to cite or link to this item:
https://hdl.handle.net/1959.11/28258
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Eshragh, Ali | en |
dc.contributor.author | Filar, Jerzy A | en |
dc.contributor.author | Kalinowski, Thomas | en |
dc.contributor.author | Mohammadian, Sogol | en |
dc.date.accessioned | 2020-03-27T03:44:19Z | - |
dc.date.available | 2020-03-27T03:44:19Z | - |
dc.date.issued | 2020-05 | - |
dc.identifier.citation | Mathematics of Operations Research, 45(2), p. 713-731 | en |
dc.identifier.issn | 1526-5471 | en |
dc.identifier.issn | 0364-765X | en |
dc.identifier.uri | https://hdl.handle.net/1959.11/28258 | - |
dc.description.abstract | 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. | en |
dc.language | en | en |
dc.publisher | Institute for Operations Research and the Management Sciences (INFORMS) | en |
dc.relation.ispartof | Mathematics of Operations Research | en |
dc.title | Hamiltonian Cycles and Subsets of Discounted Occupational Measures | en |
dc.type | Journal Article | en |
dc.identifier.doi | 10.1287/moor.2019.1009 | en |
local.contributor.firstname | Ali | en |
local.contributor.firstname | Jerzy A | en |
local.contributor.firstname | Thomas | en |
local.contributor.firstname | Sogol | en |
local.relation.isfundedby | ARC | en |
local.subject.for2008 | 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | en |
local.subject.seo2008 | 970101 Expanding Knowledge in the Mathematical Sciences | en |
local.profile.school | School of Science and Technology | en |
local.profile.email | tkalinow@une.edu.au | en |
local.output.category | C1 | en |
local.grant.number | DP150100618 | en |
local.grant.number | DP160101236 | en |
local.record.place | au | en |
local.record.institution | University of New England | en |
local.publisher.place | United States of America | en |
local.format.startpage | 713 | en |
local.format.endpage | 731 | en |
local.identifier.scopusid | 85072255132 | en |
local.peerreviewed | Yes | en |
local.identifier.volume | 45 | en |
local.identifier.issue | 2 | en |
local.contributor.lastname | Eshragh | en |
local.contributor.lastname | Filar | en |
local.contributor.lastname | Kalinowski | en |
local.contributor.lastname | Mohammadian | en |
dc.identifier.staff | une-id:tkalinow | en |
local.profile.orcid | 0000-0002-8444-6848 | en |
local.profile.role | author | en |
local.profile.role | author | en |
local.profile.role | author | en |
local.profile.role | author | en |
local.identifier.unepublicationid | une:1959.11/28258 | en |
local.date.onlineversion | 2019-11-27 | - |
dc.identifier.academiclevel | Academic | en |
dc.identifier.academiclevel | Academic | en |
dc.identifier.academiclevel | Academic | en |
dc.identifier.academiclevel | Academic | en |
local.title.maintitle | Hamiltonian Cycles and Subsets of Discounted Occupational Measures | en |
local.output.categorydescription | C1 Refereed Article in a Scholarly Journal | en |
local.relation.url | http://arxiv.org/abs/1805.04725v2 | en |
local.relation.grantdescription | ARC/DP150100618 | en |
local.search.author | Eshragh, Ali | en |
local.search.author | Filar, Jerzy A | en |
local.search.author | Kalinowski, Thomas | en |
local.search.author | Mohammadian, Sogol | en |
local.istranslated | No | en |
local.uneassociation | Yes | en |
local.atsiresearch | No | en |
local.sensitive.cultural | No | en |
local.identifier.wosid | 000531094600014 | en |
local.year.available | 2019 | en |
local.year.published | 2020 | en |
local.fileurl.closedpublished | https://rune.une.edu.au/web/retrieve/119a55a0-d76e-4486-91d4-f261e3553084 | en |
local.subject.for2020 | 490404 Combinatorics and discrete mathematics (excl. physical combinatorics) | en |
local.subject.seo2020 | 280118 Expanding knowledge in the mathematical sciences | en |
Appears in Collections: | Journal Article School of Science and Technology |
Files in This Item:
File | Description | Size | Format |
---|
SCOPUSTM
Citations
3
checked on Nov 25, 2023
Page view(s)
1,374
checked on Sep 3, 2023
Download(s)
2
checked on Sep 3, 2023
Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.