Complete Convergence of the Directed TSP

From MaRDI portal





The directed travelling salesman problem (TSP) is considered. The random directed graph \(G_ n\) is defined in such a way that its vertices \(X_ 1,\dots,X_ n\) are independent uniformly distributed over \([0,1]^ 2\), while the orientation of the edge \(X_ i X_ j\) is selected at random, independently for each edge and independently of \(X_ i\)'s, according to Bernoulli r.v. The author proves that there is a complete convergence of the variables \(n^{-1/2}U_ n\) (where \(U_ n\) is the length of the directed shortest path through \(x_ 1,\dots,x_ n\) (vertices of \(G\))) to some universal constant \(\beta\), i.e. that \[ \sum_{n\geq 1}P\left(\left|{U_ n \over \sqrt {n}}-\beta\right|>\varepsilon\right)<\infty; \qquad \forall\varepsilon>0. \] Similar results was previously known for the undirected TSP. The proof of the theorems for the directed case are based on the examination of martingale difference sequences associated to \(U_ n\).











This page was built for publication: Complete Convergence of the Directed TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3989822)