{"43783":{"#nid":"43783","#data":{"type":"event","title":"Markov Chains \u0026 Optimality of the Hamiltonian Cycle","body":[{"value":"\u003Cp\u003E\u003Cem\u003EPresentation\u003C\/em\u003E: \u003Cstrong\u003EMarkov Chains \u0026amp; Optimality of the Hamiltonian Cycle\u003C\/strong\u003E\n\u003C\/p\u003E\n\u003Cp\u003E\u003Cem\u003EAbstract\u003C\/em\u003E: We consider the Hamiltonian cycle problem (HCP) embedded in a controlled Markov decision process. In this setting, HCP reduces to an optimization problem on a set of Markov chains corresponding to a given graph. We prove that Hamiltonian cycles are minimizers for the trace of the fundamental matrix on a set of all stochastic transition matrices. In case of doubly stochastic matrices with symmetric linear perturbation, we show that Hamiltonian cycles minimize a diagonal element of a fundamental matrix for all admissible values of the perturbation parameter. In contrast to the previous work on this topic, our arguments are primarily based on probabilistic rather than algebraic methods.\n\u003C\/p\u003E\n\u003Cp\u003EJoint work with Vladimir Ejov\n\u003C\/p\u003E\n\u003Cp\u003E\u003Cem\u003EBio:\u003C\/em\u003E  Nelly Litvak is an Assistant Professor at the University of Twente, The Netherlands, in the Stochastic Operations Research group. Her research interests are in stochastic networks, popularity measures and probabilistic ranking schemes in complex networks, queueing theory, perturbed Markov chains, queueing models in health care logistics, performance analysis of carousel systems.\n\u003C\/p\u003E\n\u003Cp\u003EFor more information, visit: \u003Ca href=\u0027http:\/\/wwwhome.math.utwente.nl\/~litvakn\/\u0027\u003Ehttp:\/\/wwwhome.math.utwente.nl\/~litvakn\/\u003C\/a\u003E\n\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"Markov Chains \u0026amp; Optimality of the Hamiltonian Cycle","format":"limited_html"}],"field_summary_sentence":[{"value":"Markov Chains \u0026 Optimality of the Hamiltonian Cycle"}],"uid":"27279","created_gmt":"2009-10-12 21:20:17","changed_gmt":"2016-10-08 01:47:54","author":"Barbara Christopher","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2008-04-01T12:00:00-04:00","event_time_end":"2008-04-01T13:00:00-04:00","event_time_end_last":"2008-04-01T13:00:00-04:00","gmt_time_start":"2008-04-01 16:00:00","gmt_time_end":"2008-04-01 17:00:00","gmt_time_end_last":"2008-04-01 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[],"keywords":[{"id":"5981","name":"Markov Chains \u0026 Optimality of the Hamiltonian Cycle"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cstrong\u003EMaria Vlasiou\u003C\/strong\u003E\u003Cbr \/\u003EISyE\u003Cbr \/\u003E\u003Ca href=\u0022mailto:vlasiou@gatech.edu\u0022\u003EContact Maria Vlasiou\u003C\/a\u003E\u003Cbr \/\u003E\u003Cstrong\u003E404-385-6752\u003C\/strong\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}