Worst case asymptotics for some classical optimization problems (Q1375702)

From MaRDI portal
Revision as of 15:11, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references