Quantizers ad the worst case Euclidean traveling salesman problem

DOI10.1016/0095-8956(90)90097-JzbMath0658.90089MaRDI QIDQ1111946

Luis A. Goddyn

Publication date: 1990

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

upper boundsasymptotic behaviorprobabilistic analysisquantizersworst case analysisEuclidean traveling salesman

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items (4)

Worst-case minimum rectilinear Steiner trees in all dimensions ⋮ Worst-case demand distributions in vehicle routing ⋮ Sigma-delta quantization errors and the traveling salesman problem ⋮ Last-Mile Shared Delivery: A Discrete Sequential Packing Approach

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the length of optimal TSP circuits in sets of bounded diameter
• A partitioning algorithm for minimum weighted Euclidean matching
• On Steiner trees for bounded point sets
• The Euclidean traveling salesman problem is NP-complete
• Über einen geometrischen Satz
• On the Voronoi Regions of Certain Lattices
• A lower bound on the average error of vector quantizers (Corresp.)
• The shortest path and the shortest road through n points
• Euclidean matching problems and the metropolis algorithm
• Extremum Properties of Hexagonal Partitioning and the Uniform Distribution in Euclidean Location
• The Voronoi Region of $E_7^*$
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• The hexagon theorem
• Asymptotic quantization error of continuous signals and the quantization dimension
• A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One
• Voronoi regions of lattices, second moments of polytopes, and quantization
• Fast quantizing and decoding and algorithms for lattice quantizers and codes
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• Probabilistic Analysis of Partitioning Algorithms for the Traveling-Salesman Problem in the Plane
• Asymptotically optimal block quantization
• How Long Can a Euclidean Traveling Salesman Tour Be?
• The Optimal Lattice Quantizer in Three Dimensions
• Probabilistic and Worst Case Analyses of Classical Problems of Combinatorial Optimization in Euclidean Space
• On the Shortest Path Through a Number of Points

This page was built for publication: Quantizers ad the worst case Euclidean traveling salesman problem