{"id":82,"date":"2020-01-17T09:29:23","date_gmt":"2020-01-16T22:59:23","guid":{"rendered":"http:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/?page_id=82"},"modified":"2020-01-17T12:08:38","modified_gmt":"2020-01-17T01:38:38","slug":"random-walk-approach","status":"publish","type":"page","link":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/","title":{"rendered":"Random walk approach"},"content":{"rendered":"

[vc_row][vc_column][vc_empty_space][vc_column_text]<\/p>\n

Random walk approach<\/h1>\n

Exploiting a result due to Feinberg [6], we can constrain the set of discounted occupational measures (in a Mfarkov decision process induced by a given graph) by a single cut, and make a simple normalization to construct a polytope H<\/b>\u03b2<\/sub><\/i> that is nonempty whenever the graph is Hamiltonian and which – in a prescribed sense – contains all the Hamiltonian cycles among its extreme points. While the latter polytope has been exploited as a base for two successful heuristic algorithms (e.g. see [1], [5]), we have evidence that it may also reveal certain fundamental properties of Hamiltonian graphs, when the parameter \u03b2<\/i> is sufficiently near 1.<\/p>\n

In particular, we can construct two smaller polytopes WH<\/b>\u03b2<\/sub><\/i> and WH<\/b>p<\/sup>\u03b2<\/sub><\/i> such that WH<\/b>p<\/sup>\u03b2<\/sub><\/i> \u2282 WH<\/b>\u03b2<\/sub><\/i> \u2282 H<\/b>\u03b2<\/sub><\/i> and, more importantly, the only extreme points that WH<\/b>p<\/sup>\u03b2<\/sub><\/i> and H<\/b>\u03b2<\/sub><\/i> have in common correspond precisely to Hamiltonian cycles. This is, schematically, portrayed in the figure below.\u00a0Recently, Filar and Eshragh [4] designed a random walk, pivoting, algorithm on the extreme points of WH<\/b>p<\/sup>\u03b2<\/sub><\/i> and H<\/b>\u03b2<\/sub><\/i> that in – numerical testing – found Hamiltonian cycles in 2 to 34 random pivots for randomly generated (sparse) graphs with number of vertices ranging from 20 to 150.<\/p>\n

[\/vc_column_text][vc_empty_space][vc_single_image image=”56″ img_size=”full” alignment=”center”][vc_empty_space][vc_column_text]<\/p>\n

As expected, the above random walk algorithm will find a Hamiltonian cycle (if there is one) in finite time, with probability one (see [4]). However, what makes this idea exciting is that the observed slow growth of the number of random pivots in\u00a0N<\/i> (number of vertices) suggests that the following, much more powerful, result may also be true.<\/p>\n

Conjecture<\/b>: Let\u00a0A<\/i><\/b> be a suitably designed random walk algorithm and\u00a0Y be the random variable denoting the number of extreme points that A<\/i><\/b> will need to examine to identify a Hamiltonian cycle (if there is one). Then there exist polynomials q1<\/sub><\/i>(log(\u03b2<\/i>), N<\/i>) and q2<\/sub><\/i>(log(\u03b2<\/i>), N<\/i>) (with positive coefficients of the leading power of N<\/i>) such that for \u03b2<\/i> sufficiently near 1, the probability Pr(Y > q1<\/sub><\/i>(log(\u03b2<\/i>), N<\/i>)) \u2264 exp{-q2<\/sub><\/i>(log(\u03b2<\/i>), N<\/i>)}.<\/p>\n

These results were first derived in Eshragh’s PhD thesis\u00a0[2] which was later\u00a0published as [3].<\/p>\n

PUBLICATIONS<\/h3>\n

[1] Ejov, V., Filar, J.A., Haythorpe, M. and Nguyen, G.T. “Refined MDP-based branch-and-fix algorithm for the Hamiltonian Cycle Problem.” Mathematics of Operations Research<\/i>, 34(3):758-768, 2009. ACM Digital Library<\/a><\/span><\/span><\/p>\n

[2] Eshragh, A. “Hamiltonian cycles and the space of discounted occupational measures.” University of South Australia, 2011. Trove<\/a><\/p>\n

[3] Eshragh, A. “Hamiltonian Cycles and the Space of Discounted Occupational Measure.” Lambert Academic Publishers, Saarbr\u00fccken, 2011.<\/p>\n

[4] Eshragh, A. and Filar, J.A. “Hamiltonian Cycles, Random Walks, and Discounted Occupational Measures.” Mathematics of Operations Research<\/i>, 36(2):258-270, 2011. Informs Online<\/a><\/p>\n

[5] Eshragh, A., Filar, J.A. and Haythorpe, M. “A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem.” Annals of Operations Research<\/i>, 189(1):103-125, 2011. SpringerLink<\/a><\/p>\n

[6] Feinberg, E. “Constrained discounted Markov decision processes and Hamiltonian cycles.” Mathematics of Operations Research<\/i>, 25(1):130-140, 2000. JSTOR<\/a>[\/vc_column_text][vc_empty_space][\/vc_column][\/vc_row]<\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"

[vc_row][vc_column][vc_empty_space][vc_column_text] Random walk approach Exploiting a result due to Feinberg [6], we can constrain the set of discounted occupational measures (in a Mfarkov decision process induced by a given graph) by a single cut, and make a simple normalization to construct a polytope H\u03b2 that is nonempty whenever the graph is Hamiltonian and which – […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":63,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-82","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/82","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/comments?post=82"}],"version-history":[{"count":0,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/82\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/pages\/63"}],"wp:attachment":[{"href":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/wp-json\/wp\/v2\/media?parent=82"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}