Quantizers ad the worst case Euclidean traveling salesman problem
type: Item
instance of: scholarly article
title: Quantizers ad the worst case Euclidean traveling salesman problem
zbMATH Open document ID: 0658.90089
DOI: 10.1016/0095-8956(90)90097-J
author: Luis Goddyn
published in: Journal of Combinatorial Theory. Series B
publication date: 1990-01-01T00:00:00Z
review text: For \(k\geq 2\) we consider a worst-case instance of the Euclidean traveling salesman problem through n points in the unit k-cube \([0,1]^ k\). That is, for each n we arrange n points in the k-cube so that the shortest circuit containing them is as long as possible. Such optimum circuits are known to have length asymptotic to \(\alpha_ k\sqrt{k}n^{(k-1)/k}\) as \(n\to \infty\), where \(\alpha_ k\) depends only on k and is bounded. We are concerned with the problem of determining \(\alpha_ k\), for small values of k and also the asymptotic behavior of \(\alpha_ k\) as \(k\to \infty\). It was shown by \textit{L. Few} [Mathematika 2, 141-144 (1955; Zbl 0067.126)] that \(3^{-1/4}\leq \alpha_ 2\leq 1\) and that for \(k\geq 3\), \[ (\Gamma (1+k/2))^{-1/k}(\pi k)^{-1/2}\leq \alpha_ k \leq k^{1/2}(2^{-1/2}(k-1)^{-1/2})^{((k-2)/k)} \] so that, for large k, \(0.2419\lesssim \alpha_ k\lesssim 0.7071\). Later, \textit{S. Moran} [J. Comb. Theory, Ser. B 37, 113-141 (1984; Zbl 0557.52008)] improved the upper bound, for large k, to \(\alpha_ k\lesssim 0.6136\). Few's upper bound is better than Moran's for small values of k. Here, we sharpen each of these upper bounds by a factor of about \(\sqrt{2}\). By generalizing the classic ``strip'' algorithm used by Few, we obtain \[ \alpha_ k\leq k^{1/2}(2\gamma_{k-1})^{((k-1)/k)} \] where \(\gamma_ k\) is the mean deviation per dimension of the best quantizer of unit density in \({\mathbb{E}}^ k\) [for the study of quantizers see the papers in IEEE Trans. Inf. Theory IT-28, No.2 (1982), in particular \textit{P. L. Zador}, ibid., 139-149 (1982; Zbl 0476.94008)]. \(\gamma_ k\) can be roughly defined as follows: Let R be a very large k- dimensional cube with integer volume M, and let z be a uniformly distributed random point in R. Then \(\gamma_ k\) is the least possible expected value of \((1/k)\| z-Q(z)\|_ 2\), over all functions Q from R onto an M-subset of R (Q is called a quantizer for R). Numerically, we have \(\gamma_ 1=0.25\), \(\gam…
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 4076988
zbMATH Keywords: worst case analysis
zbMATH Keywords: probabilistic analysis
zbMATH Keywords: Euclidean traveling salesman
zbMATH Keywords: asymptotic behavior
zbMATH Keywords: upper bounds
zbMATH Keywords: quantizers
MaRDI profile type: Publication
cites work: The Optimal Lattice Quantizer in Three Dimensions
cites work: Q5729634
cites work: On Steiner trees for bounded point sets
cites work: A lower bound on the average error of vector quantizers (Corresp.)
cites work: Voronoi regions of lattices, second moments of polytopes, and quantization
cites work: Fast quantizing and decoding and algorithms for lattice quantizers and codes
cites work: On the Voronoi Regions of Certain Lattices
cites work: Q4039784
cites work: A partitioning algorithm for minimum weighted Euclidean matching
cites work: Über einen geometrischen Satz
cites work: Q3316129
cites work: Q5344631
cites work: The shortest path and the shortest road through n points
cites work: Asymptotically optimal block quantization
cites work: Extremum Properties of Hexagonal Partitioning and the Uniform Distribution in Euclidean Location
cites work: A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
cites work: How Long Can a Euclidean Traveling Salesman Tour Be?
cites work: Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
cites work: Q3707785
cites work: On the length of optimal TSP circuits in sets of bounded diameter
cites work: The hexagon theorem
cites work: The Euclidean traveling salesman problem is NP-complete
cites work: Q5568974
cites work: Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
cites work: Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
cites work: The Travelling Salesman Problem and Minimum Matching in the Unit Square
cites work: On the Shortest Path Through a Number of Points
cites work: Euclidean matching problems and the metropolis algorithm
cites work: Q3030892
cites work: The Voronoi Region of $E_7^*$
cites work: Asymptotic quantization error of continuous signals and the quantization dimension
Recommended article: Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem
Recommended article: The Traveling Salesman Problem under squared Euclidean distances
Recommended article: A Priori Bounds on the Euclidean Traveling Salesman
Recommended article: Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
Recommended article: The travelling salesman problem and adiabatic quantum computation: an algorithm
Recommended article: Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
Recommended article: Equidistribution in all Dimensions of Worst-case Point Sets for the Traveling Salesman Problem
Recommended article: A Polyhedral Study of the Quadratic Traveling Salesman Problem
Recommended article: Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
Recommended article: Hard to solve instances of the Euclidean traveling salesman problem
description: scientific article; zbMATH DE number 4076988