Spacefilling curves and the planar travelling salesman problem

DOI10.1145/76359.76361MaRDI QIDQ3474889zbMATH OpenOpenAlexFDO

Authors L. K. Platzman, John J. III Bartholdi

Publication date 1989

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/76359.76361

zbMATH Keywords

fractal geometryrouting and layoutsequencing and schedulingspacefilling curves

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 4087452
• The Euclidean traveling salesman problem and a space-filling curve
• General spacefilling curve heuristics and limit theory for the traveling salesman problem
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
• Genetically improved presequences for Euclidean traveling salesman problems

Cited in

(48)

• Submodularity and the traveling salesman problem
• The Guilty net for the traveling salesman problem
• Constructing competitive tours from local information
• General spacefilling curve heuristics and limit theory for the traveling salesman problem
• Genetically improved presequences for Euclidean traveling salesman problems
• Neural methods for the traveling salesman problem: Insights from operations research
• The Euclidean traveling salesman problem and a space-filling curve
• Solving large-scale TSP using a fast wedging insertion partitioning approach
• Routing heuristics for automated pick and place machines
• On properties of geometric random problems in the plane
• Sampling multidimensional signals by a new class of quasi-random sequences
• An information global minimization algorithm using the local improvement technique
• Division rules for tissue P systems inspired by space filling curves
• Sorting methods and convergence rates for Array-RQMC: some empirical comparisons
• Bounds for the traveling salesman paths of two-dimensional modular lattices
• Novel concave hull-based heuristic algorithm for TSP
• Efficacy of spacefilling heuristics in Euclidean combinatorial optimization
• Worst-case examples for the spacefilling curve heuristic for the Euclidean traveling salesman problem
• Strict s-numbers of non-compact Sobolev embeddings into continuous functions
• Indian kolam patterns, sand drawings in the Vanuatu Islands, the Sierpiński curve, and monoid morphisms
• Compact Hilbert indices: space-filling curves for domains with unequal side lengths
• ``Conscientious neural nets for tour construction in the traveling salesman problem: The vigilant net
• Practical distribution-sensitive point location in triangulations
• Traveling salesman-based curve reconstruction in polynomial time
• Van der Corput and Golden ratio sequences along the Hilbert space-filling curve
• A distribution-free TSP tour length estimation model for random graphs
• Nearest-neighbor graphs on the cantor set
• WORST-CASE ANALYSIS FOR PLANAR MATCHING AND TOUR HEURISTICS WITH BUCKETING TECHNIQUES AND SPACEFILLING CURVES
• Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space
• scientific article; zbMATH DE number 4087452 (Why is no real title available?)
• Sums of Squares of Edge Lengths and Spacefilling Curve Heuristics for the Traveling Salesman Problem
• Applications of the space — filling curves with data driven measure — preserving property
• scientific article; zbMATH DE number 1445366 (Why is no real title available?)
• Designing networks with good equilibria under uncertainty
• Assouad-Nagata dimension and gap for ordered metric spaces
• Plane-Filling Trails (Media Exposition)
• Universal Algorithms for Clustering Problems
• Spaces that can be ordered effectively: virtually free groups and hyperbolicity
• An improved upper bound for the universal TSP on the grid
• Scattering and sparse partitions, and their applications
• Optimal padded decomposition for bounded treewidth graphs
• Scattering and sparse partitions, and their applications
• Match twice and stitch: a new TSP tour construction heuristic.
• Universal algorithms for clustering problems
• Reptilings and space-filling curves for acute triangles
• Lower bounds for the universal TSP on the plane
• Algorithms for the universal and a priori TSP
• Lipschitz and Hölder global optimization using space-filling curves

This page was built for publication: Spacefilling curves and the planar travelling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474889)