Worst case asymptotics for some classical optimization problems
The author considers methods for obtaining the worst case asymptotics of some classical problems in combinatorial optimization and operations research. The attention is focussed on the following processes: 1. Minimal spinning trees (MST). \( M(x_{1},x_{2},\dots,x_{n}):=\min_{T} \sum_{e \in T } |e |, \) where the minimum is over all connected graphs \(T\) with vertex set \(V\) and \(|e|\) denotes the Euclidean length of edge \(e\). 2. Travelling salesman problem (TSP). For \(\alpha > 0\) the TSP process on the vertex set \(V\) with \(\alpha\)th power weighted edges is given by \( T^{\alpha}(V):= \min_{T} \sum_{e \in T } |e |^{\alpha}, \) where the minimum is over all tours \(T\) on the vertex set \(V\). 3. Minimal matching. For \(\alpha > 0\) the minimal matching on \(V\) with \(\alpha\)th power weighted edges is given by \( S^{\alpha}(V):= \min_{\varrho} \sum_{i=1 }^{n/2} |x_{\varrho(2i-1)}-x_{\varrho(2i)} |^{\alpha}, \) where \(|. |\) denotes Euclidean norm and where the minimum is over all permutations of integers \(1,2,\dots,n,\) and where \(n\) is assumed to have even parity. \smallskip \noindent The key simplifying idea involves consideration of the associated ``boundary processes. The approach taken in the paper consists of the following two natural ideas: (i) given a Euclidean process, use superadditivity to find the worst case asymptotics for the canonical ``boundary process and (ii) use a dyadic subdivision of the cube to show that the Euclidean process is close to the boundary process.
- Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
- Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
- scientific article; zbMATH DE number 4167872
- An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
- Worst case asymptotics of power-weighted Euclidean functionals
- Asymptotics for Euclidean functionals with power-weighted edges
- Asymptotics for the Euclidean TSP with power weighted edges
- Ergodic theorems for some classical problems in combinatorial optimization
- scientific article; zbMATH DE number 3193293 (Why is no real title available?)
- Limit theorems and rates of convergence for Euclidean functionals
- Subadditive Euclidean functionals and nonlinear growth in geometric probability
- Worst-case greedy matchings in the unitd-cube
- Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
- Combinatorial optimization problems in ultrametric spaces
- The minimal spanning tree and the upper box dimension
- scientific article; zbMATH DE number 4167872 (Why is no real title available?)
- Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
- On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\)
- A quadratic version of the traveling salesman problem
This page was built for publication: Worst case asymptotics for some classical optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1375702)
