Probability theory of classical Euclidean optimization problems
From MaRDI portal
The monograph aims to develop the probability theory of solutions to the classical problems in Euclidean combinatorial optimization, computational geometry, and operations research. These problems are associated with graphs and the chief goal is to describe the almost sure behavior of the total edge lengths of these graphs. The book consists of the following chapters: 1. Introduction. 2. Subadditivity and superadditivity. 3. Subadditive and superadditive Euclidean functionals. 4. Asymptotics for Euclidean functionals: The uniform case. 5. Rates of convergence and heuristics. 6. Isoperimetry and concentration inequalities. 7. Umbrella theorems for Euclidean functionals. 8. Applications and examples. 9. Minimal triangulations. 10. Geometric location problems. 11. Worst case growth rates.
Recommendations
- scientific article; zbMATH DE number 176071
- Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
- Rates of Convergence for Quasi-Additive Smooth Euclidean Functionals and Application to Combinatorial Optimization Problems
- Limit theorems and rates of convergence for Euclidean functionals
Cited in
(88)- A simple measure of conditional dependence
- Asymptotics for the length of a minimal triangulation on a random sample
- An asymptotic theory for recurrence relations based on minimization and maximization.
- Rate of convergence of power-weighted Euclidean minimal spanning trees
- Covering algorithms, continuum percolation and the geometry of wireless networks
- Asymptotic of power-weighted Euclidean functionals
- Asymptotics for weighted minimal spanning trees on random points
- Asymptotics for Voronoi tessellations on random samples
- The scaling limits of the minimal spanning tree and invasion percolation in the plane
- A PDE approach to a 2-dimensional matching problem
- Asymptotic properties of combinatorial optimization problems in \(p\)-adic space
- Gaussian limits for random measures in geometric probability
- Weak laws of large numbers in geometric probability
- Vertex ordering and partitioning problems for random spatial graphs.
- Computing the variance of tour costs over the solution space of the TSP in polynomial time
- Smoothed analysis of partitioning algorithms for Euclidean functionals
- Minimum spanning trees of random geometric graphs with location dependent weights
- Some results on the optimal matching problem for the Jacobi model
- A simple Fourier analytic proof of the AKT optimal matching theorem
- Limit theory of combinatorial optimization for random geometric graphs
- Quantitative two-scale stabilization on the Poisson space
- Euclidean travelling salesman problem with location-dependent and power-weighted edges
- On the quadratic random matching problem in two-dimensional domains
- A fluctuation result for the displacement in the optimal matching problem
- Convergence of asymptotic costs for random Euclidean matching problems
- Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
- Local angles and dimension estimation from data on manifolds
- On optimal matching of Gaussian samples
- On the choice of weight functions for linear representations of persistence diagrams
- Generating subtour elimination constraints for the TSP from pure integer solutions
- Optimal flow through the disordered lattice
- The radial spanning tree of a Poisson point process
- Rates of convergence of means of Euclidean functionals
- Multivariate spatial central limit theorems with applications to percolation and spatial graphs
- Combinatorial Optimization Over Two Random Point Sets
- Central limit theorems for the radial spanning tree
- Limit theorems for random spatial drainage networks
- Randomized near-neighbor graphs, giant components and applications in data science
- Coulomb gases under constraint: some theoretical and numerical results
- Probabilistic analysis for a multiple depot vehicle routing problem
- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
- Random parking, Euclidean functionals, and rubber elasticity
- Explicit laws of large numbers for random nearest-neighbour-type graphs
- Nearest-neighbor graphs on the cantor set
- On the greedy walk problem
- Optimal random matchings, tours, and spanning trees in hierarchically separated trees
- Limit theory for point processes in manifolds
- Intrinsic dimension identification via graph-theoretic methods
- scientific article; zbMATH DE number 176071 (Why is no real title available?)
- On the variance of the random sphere of influence graph
- The saga of minimum spanning trees
- Asymptotics for Euclidean functionals of mixing processes
- Random minimal directed spanning trees and Dickman-type distributions
- On the largest common subtree of random leaf-labeled binary trees
- THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
- Sub-tree counts on hyperbolic random geometric graphs
- k-variance: a clustered notion of variance
- Random geometric complexes in the thermodynamic regime
- Macroscopic and edge behavior of a planar jellium
- A fractal dimension for measures via persistent homology
- One-dimensional empirical measures, order statistics, and Kantorovich transport distances
- Circular law for random matrices with unconditional log-concave distribution
- Distribution-sensitive construction of the greedy spanner
- Limit theorems in discrete stochastic geometry
- The stretch-length tradeoff in geometric networks: average case and worst case study
- Short-length routes in low-cost networks via Poisson line patterns
- Limit theory for the random on‐line nearest‐neighbor graph
- Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
- Rooted edges of a minimal directed spanning tree on random points
- On the total length of the random minimal directed spanning tree
- Geodesics and flows in a Poissonian city
- Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
- Probabilistic properties of highly connected random geometric graphs
- Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
- Rates of multivariate normal approximation for statistics in geometric probability
- Upper large deviations for power-weighted edge lengths in spatial random networks
- Correction: A class of Rényi information estimators for multidimensional densities
- Normal approximation for statistics of randomly weighted complexes
- On minimum spanning trees for random Euclidean bipartite graphs
- Smoothed analysis of the 2-opt heuristic for the TSP under Gaussian noise
- Design of computer experiments: space filling and beyond
- Central limit theorem for Euclidean minimal spanning acycles
- A quadratic version of the traveling salesman problem
- Near-minimal spanning trees: A scaling exponent in probability models
- Note on the structure of Kruskal's algorithm
- Concentration inequalities for random fields via coupling
- Connected spatial networks over random points and a route-length statistic
- A new method of normal approximation
This page was built for publication: Probability theory of classical Euclidean optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1385435)
