{"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":"<div class=\"wpb-content-wrapper\" id=\"wpb-content-root\"><p>[vc_row][vc_column][vc_empty_space][vc_column_text]<\/p>\n<h1>Random walk approach<\/h1>\n<p align=\"left\">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 <b>H<\/b><i><sub>\u03b2<\/sub><\/i> that is nonempty whenever the graph is Hamiltonian and which &#8211; in a prescribed sense &#8211; 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 <i>\u03b2<\/i> is sufficiently near 1.<\/p>\n<p align=\"left\">In particular, we can construct two smaller polytopes <b>WH<\/b><i><sub>\u03b2<\/sub><\/i> and <b>WH<\/b><i><sup>p<\/sup><sub>\u03b2<\/sub><\/i> such that <b>WH<\/b><i><sup>p<\/sup><sub>\u03b2<\/sub><\/i> \u2282 <b>WH<\/b><i><sub>\u03b2<\/sub><\/i> \u2282 <b>H<\/b><i><sub>\u03b2<\/sub><\/i> and, more importantly, the only extreme points that <b>WH<\/b><i><sup>p<\/sup><sub>\u03b2<\/sub><\/i> and <b>H<\/b><i><sub>\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 <b>WH<\/b><i><sup>p<\/sup><sub>\u03b2<\/sub><\/i> and <b>H<\/b><i><sub>\u03b2<\/sub><\/i> that in &#8211; numerical testing &#8211; 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<p>[\/vc_column_text][vc_empty_space][vc_single_image image=&#8221;56&#8243; img_size=&#8221;full&#8221; alignment=&#8221;center&#8221;][vc_empty_space][vc_column_text]<\/p>\n<p align=\"left\">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\u00a0<i>N<\/i> (number of vertices) suggests that the following, much more powerful, result may also be true.<\/p>\n<p align=\"left\"><b>Conjecture<\/b>: Let\u00a0<b><i>A<\/i><\/b> be a suitably designed random walk algorithm and\u00a0Y be the random variable denoting the number of extreme points that <b><i>A<\/i><\/b> will need to examine to identify a Hamiltonian cycle (if there is one). Then there exist polynomials <i>q<sub>1<\/sub><\/i>(log(<i>\u03b2<\/i>), <i>N<\/i>) and <i>q<sub>2<\/sub><\/i>(log(<i>\u03b2<\/i>), <i>N<\/i>) (with positive coefficients of the leading power of <i>N<\/i>) such that for <i>\u03b2<\/i> sufficiently near 1, the probability Pr(Y &gt; <i>q<sub>1<\/sub><\/i>(log(<i>\u03b2<\/i>), <i>N<\/i>)) \u2264 exp{-<i>q<sub>2<\/sub><\/i>(log(<i>\u03b2<\/i>), <i>N<\/i>)}.<\/p>\n<p align=\"left\">These results were first derived in Eshragh&#8217;s PhD thesis\u00a0[2] which was later\u00a0published as [3].<\/p>\n<h3>PUBLICATIONS<\/h3>\n<p><span class=\"doi\"><span class=\"value\">[1] Ejov, V., Filar, J.A., Haythorpe, M. and Nguyen, G.T. &#8220;Refined MDP-based branch-and-fix algorithm for the Hamiltonian Cycle Problem.&#8221; <i>Mathematics of Operations Research<\/i>, 34(3):758-768, 2009. <a href=\"http:\/\/dl.acm.org\/citation.cfm?id=1599468\" target=\"_blank\" rel=\"noopener noreferrer\">ACM Digital Library<\/a><\/span><\/span><\/p>\n<p>[2] Eshragh, A. &#8220;Hamiltonian cycles and the space of discounted occupational measures.&#8221; University of South Australia, 2011. <a href=\"http:\/\/trove.nla.gov.au\/work\/157668907?q=Hamiltonian+cycles+and+the+space+of+discounted+occupational+measures++Ali+Eshragh+Jahromi&amp;c=book\" target=\"_blank\" rel=\"noopener noreferrer\">Trove<\/a><\/p>\n<p>[3] Eshragh, A. &#8220;Hamiltonian Cycles and the Space of Discounted Occupational Measure.&#8221; Lambert Academic Publishers, Saarbr\u00fccken, 2011.<\/p>\n<p>[4] Eshragh, A. and Filar, J.A. &#8220;Hamiltonian Cycles, Random Walks, and Discounted Occupational Measures.&#8221; <i>Mathematics of Operations Research<\/i>, 36(2):258-270, 2011. <a href=\"http:\/\/mor.journal.informs.org\/content\/36\/2\/258.short\" target=\"_blank\" rel=\"noopener noreferrer\">Informs Online<\/a><\/p>\n<p>[5] Eshragh, A., Filar, J.A. and Haythorpe, M. &#8220;A hybrid simulation-optimization algorithm for the Hamiltonian cycle problem.&#8221; <i>Annals of Operations Research<\/i>, 189(1):103-125, 2011. <a href=\"http:\/\/www.springerlink.com\/content\/q774uu148g525356\/\" target=\"_blank\" rel=\"noopener noreferrer\">SpringerLink<\/a><\/p>\n<p>[6] Feinberg, E. &#8220;Constrained discounted Markov decision processes and Hamiltonian cycles.&#8221; <i>Mathematics of Operations Research<\/i>, 25(1):130-140, 2000. <a href=\"http:\/\/www.jstor.org\/pss\/3690427\" target=\"_blank\" rel=\"noopener noreferrer\">JSTOR<\/a>[\/vc_column_text][vc_empty_space][\/vc_column][\/vc_row]<\/p>\n<\/div>","protected":false},"excerpt":{"rendered":"<p>[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 &#8211; [&hellip;]<\/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"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.8 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Random walk approach - Flinders Hamiltonian Cycle Project<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Random walk approach - Flinders Hamiltonian Cycle Project\" \/>\n<meta property=\"og:description\" content=\"[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 &#8211; [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/\" \/>\n<meta property=\"og:site_name\" content=\"Flinders Hamiltonian Cycle Project\" \/>\n<meta property=\"article:modified_time\" content=\"2020-01-17T01:38:38+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/random-walk-approach\\\/\",\"url\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/random-walk-approach\\\/\",\"name\":\"Random walk approach - Flinders Hamiltonian Cycle Project\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/#website\"},\"datePublished\":\"2020-01-16T22:59:23+00:00\",\"dateModified\":\"2020-01-17T01:38:38+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/random-walk-approach\\\/#breadcrumb\"},\"inLanguage\":\"en-AU\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/random-walk-approach\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/random-walk-approach\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"HCP APPROACHES\",\"item\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/hcp-approaches\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Random walk approach\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/#website\",\"url\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/\",\"name\":\"Flinders Hamiltonian Cycle Project\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/sites.flinders.edu.au\\\/flinders-hamiltonian-cycle-project\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-AU\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Random walk approach - Flinders Hamiltonian Cycle Project","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/","og_locale":"en_US","og_type":"article","og_title":"Random walk approach - Flinders Hamiltonian Cycle Project","og_description":"[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 &#8211; [&hellip;]","og_url":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/","og_site_name":"Flinders Hamiltonian Cycle Project","article_modified_time":"2020-01-17T01:38:38+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/","url":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/","name":"Random walk approach - Flinders Hamiltonian Cycle Project","isPartOf":{"@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/#website"},"datePublished":"2020-01-16T22:59:23+00:00","dateModified":"2020-01-17T01:38:38+00:00","breadcrumb":{"@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/#breadcrumb"},"inLanguage":"en-AU","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/random-walk-approach\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/"},{"@type":"ListItem","position":2,"name":"HCP APPROACHES","item":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/hcp-approaches\/"},{"@type":"ListItem","position":3,"name":"Random walk approach"}]},{"@type":"WebSite","@id":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/#website","url":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/","name":"Flinders Hamiltonian Cycle Project","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/sites.flinders.edu.au\/flinders-hamiltonian-cycle-project\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-AU"}]}},"_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}]}}