Assouad-Nagata dimension and gap for ordered metric spaces
From MaRDI portal
Publication:6058052
Abstract: We prove that all spaces of finite Assouad-Nagata dimension admit a good order for Travelling Salesman Problem, and provide sufficient conditions under which the converse is true. We formulate a conjectural characterisation of spaces of finite -dimension, which would yield a gap statement for the efficiency of orders on metric spaces. Under assumption of doubling, we prove a stronger gap phenomenon about all orders on a given metric space.
Recommendations
Cites work
- scientific article; zbMATH DE number 3755465 (Why is no real title available?)
- scientific article; zbMATH DE number 2012373 (Why is no real title available?)
- scientific article; zbMATH DE number 3346677 (Why is no real title available?)
- A New Short Proof of Kneser's Conjecture
- A fixed point theorem in \(L^p\)-spaces
- A proof of Alon’s second eigenvalue conjecture and related problems
- An O(N log N) planar travelling salesman heuristic based on spacefilling curves
- An improved upper bound for the universal TSP on the grid
- An optimal lower bound for hierarchical universal solutions for TSP on the plane
- Assouad-Nagata dimension of connected Lie groups
- Assouad-Nagata dimension of finitely generated \(C^\prime(\frac{1}{6})\) groups
- Assouad-Nagata dimension of locally finite groups and asymptotic cones
- Assouad-Nagata dimension of wreath products of groups
- Designing networks with good equilibria under uncertainty
- Embedding mapping class groups into a finite product of trees
- Embeddings of hyperbolic groups into products of binary trees
- Every Coxeter group acts amenably on a compact space
- Expander graphs and their applications
- Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
- How groups grow.
- Improved lower bounds for the universal and a priori TSP
- Lamplighter groups, de Brujin graphs, spider-web graphs and their spectra
- Local chromatic number, Ky Fan's theorem, and circular colorings
- Mixing and relaxation time for random walk on wreath product graphs
- Mixing times for random walks on finite lamplighter groups
- Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions
- Note on dimension theory for metric spaces
- On exactness and isoperimetric profiles of discrete groups
- Optimal lower bounds for universal and differentially private Steiner trees and TSPs
- Poincaré profiles of groups and spaces
- Ramanujan graphs
- Small cancellation labellings of some infinite graphs and applications
- Sorting in \(c \log n\) parallel steps
- Spacefilling curves and the planar travelling salesman problem
- Spaces that can be ordered effectively: virtually free groups and hyperbolicity
- Special cube complexes
- The diameter of random regular graphs
- Triangle inequalities in path metric spaces
- Universal approximations for TSP, Steiner tree, and set cover
- Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
This page was built for publication: Assouad-Nagata dimension and gap for ordered metric spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6058052)
