Ergodic theorems for some classical problems in combinatorial optimization
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.
- A matching problem and subadditive Euclidean functionals
- A new look at independence
- Asymptotics for Euclidean functionals with power-weighted edges
- Asymptotics for Euclidean minimal spanning trees on random points
- Asymptotics for the Euclidean TSP with power weighted edges
- Concentration of measure and isoperimetric inequalities in product spaces
- Ergodic theorems for superadditive processes.
- Euclidean semi-matchings of random samples
- Growth rates of Euclidean minimal spanning trees with power weighted edges
- scientific article; zbMATH DE number 4194815 (Why is no real title available?)
- scientific article; zbMATH DE number 3290003 (Why is no real title available?)
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- Limit theorems and rates of convergence for Euclidean functionals
- Multiparameter subadditive processes
- New concentration inequalities in product spaces
- Steinhaus's geometric location problem for random samples in the plane
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- The minimum spanning tree constant in geometrical probability and under the independent model: A unified approach
- Uniform pointwise ergodic theorems for classes of averaging sets and multiparameter subadditive processes
- Worst case asymptotics for some classical optimization problems
- Asymptotic properties of combinatorial optimization problems in \(p\)-adic space
- Asymptotics for Euclidean functionals with power-weighted edges
- scientific article; zbMATH DE number 4143157 (Why is no real title available?)
- scientific article; zbMATH DE number 1839489 (Why is no real title available?)
- scientific article; zbMATH DE number 6741918 (Why is no real title available?)
This page was built for publication: Ergodic theorems for some classical problems in combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2564700)
