Worst case asymptotics for some classical optimization problems (Q1375702): Difference between revisions

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.