Worst case asymptotics for some classical optimization problems
type: Item
instance of: scholarly article
title: Worst case asymptotics for some classical optimization problems
zbMATH Open document ID: 0881.05065
DOI: 10.1007/BF01271275
published in: Combinatorica
publication date: 1998-01-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 52A40
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 1102610
zbMATH Keywords: combinatorial optimization
author: J. E. Yukich
reviewed by: Erik Bajalinov
MaRDI profile type: Publication
cites work: Q5729634
cites work: Limit theorems and rates of convergence for Euclidean functionals
cites work: Asymptotics for Euclidean functionals with power-weighted edges
cites work: Worst-case greedy matchings in the unitd-cube
cites work: Subadditive Euclidean functionals and nonlinear growth in geometric probability
cites work: Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
cites work: Asymptotics for the Euclidean TSP with power weighted edges
cites work: Ergodic theorems for some classical problems in combinatorial optimization
full work available at URL: https://doi.org/10.1007/bf01271275
OpenAlex ID: W1966155527
description: scientific article; zbMATH DE number 1102610