Ergodic theorems for some classical problems in combinatorial optimization (Q2564700): Difference between revisions

Stochastic versions of various classical problems in combinatorial optimization, e.g., traveling salesman problem (TSP) and minimal spanning trees, are studied in the context of multiparameter subadditive processes indexed by \(d\)-dimensional rectangles in \(R^d\). The approach developed here is based on the key to revealing the intrinsic subadditive structure. It turns possible to apply the subadditive ergodic theorem due to M. A. Akcoglu and U. Krengel to establish relevant strong laws. Thus, for TSP, if \(\Pi\) denotes a Poisson point process with unit intensity on \(R^d\) and \(T^p(x_1, \dots, x_n)= \inf\{\sum_{e\in T} |e|^p\); \(T\) is a closed path with edges \(e\) connecting vertices \(x_k\}\), then \(\lim_{n\to\infty} T^p(\Pi\cap [0,n]^d)/n^d= \alpha(T^p,d)\) a.s. for all \(0<p\leq d\) where \(\alpha (T^d,d)\) is a finite positive constant. The paper provides also answers to several conjectures and alternative simple proofs for some known asymptotic results and poses open problems.