Jerzy A. Filar

演讲人

Centre for Industrial and Applied Mathematics(CIAM)

Jerzy A. Filar,Centre for Industrial and Applied Mathematics(CIAM),School of Mathematics and Statistics,University of South Australia,Mawson Lakes, SA 5095 Australia.

Au_61801_0.jpeg

This presentation summarizes a line of research that maps certain, notoriously hard, prob-lems of discrete mathematics - such as the Hamiltonian Cycle and the Traveling SalesmanProblems - into convex domains where continuum analysis can be carried out. Arguably, theinherent di±culty of these, now classical, problems stems precisely from the discrete natureof domains in which these problems are posed. The convexi?cation of domains underpinningthe reported results is achieved by assigning probabilistic interpretation to key elements of the original deterministic problems. In particular, approaches summarized build on a technique that embeds Hamiltonian Cycle and Traveling Salesman Problems in a structured singularly perturbed Markov Decision Process. The unifying idea is to interpret subgraphs traced out by deterministic policies as extreme points of a convex polytope in a space ?lled with randomized policies. Special attention is devoted to the subset of the latter that corresponds to all doubly stochastic probability transition matrices induced by a graph. By the famous Birkho? - von Neumann Theorem that subset is the convex hull of permutation matrices induced by the given graph. Clearly, Hamiltonian cycles (if any) are among the extreme points of this doubly stochastic polytope. The topic has now evolved to the point where there are many, both theoretical and algo-rithmic, results that exploit the nexus between graph theoretic structures and both probabilistic and algebraic entities of related Markov chains. These include moments of ?rst returntimes, limiting frequencies of visits to nodes, or the spectra of certain matrices traditionally associated with the analysis of Markov chains. There are also interesting connections with singular perturbation theory of mathematical programs and the cross-entropy method for the estimation of rare events. A number of open questions and problems will be described in the presentation. The latter will include a conject

Controlled Markov Chains, Graphs and Hamiltonicity（二）

Vod_61802.jpeg

CJFZFGB0607144407002.flv

288

350

error.html

error.html

http://gffgaf75067c2e8a043a7h9xwbb5knwkp06b5o.fbyb.hbpu.cwkeji.cn/adksvod/PublicFolder/Player

http://gffga05319f78c7994b03h9xwbb5knwkp06b5o.fbyb.hbpu.cwkeji.cn/flvServer.aspx