Worst case asymptotics for some classical optimization problems (Q1375702)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Worst case asymptotics for some classical optimization problems |
scientific article |
Statements
Worst case asymptotics for some classical optimization problems (English)
0 references
11 January 1998
0 references
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.
0 references
combinatorial optimization
0 references