Concentration for random Euclidean combinatorial optimization
Abstract
We prove concentration bounds for random Euclidean combinatorial optimization problems with $p$--costs. For bipartite matching and for the (mono- and bi-partite) traveling salesperson problem in dimension $d\ge 3$, we obtain concentration at the natural energy scale $n^{1-p/d}$ for $1\le p
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Geometric Analysis and Curvature Flows
Limits and Structures in Graph Theory
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 25 February 2026
- Language
- EN
- Document type
- Preprint