Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem

DOI10.1103/PhysRevLett.76.1188zbMath0945.90612OpenAlexW2059506221WikidataQ74569469 ScholiaQ74569469MaRDI QIDQ4492397

Allon G. Percus, Olivier C. Martin

Publication date: 16 July 2000

Published in: Physical Review Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1103/physrevlett.76.1188

zbMATH Keywords

mean-field approachnearest neighbor distribution

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (9)

Average optimal cost for the Euclidean TSP in one dimension ⋮ Vehicle Routing Algorithms for Radially Escaping Targets ⋮ The mean field traveling salesman and related problems ⋮ FINITE SIZE SCALING AND CRITICAL TRANSITION IN CONSTRAINED TRAVELING SALESMAN PROBLEM ⋮ On estimating the distribution of optimal traveling salesman tour lengths using heuristics ⋮ An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones ⋮ Statistical mechanics methods and phase transitions in optimization problems ⋮ Colloquium: Quantum annealing and analog quantum computation ⋮ New Bounds for the Traveling Salesman Constant

Cites Work

• An asymptotic determination of the minimum spanning tree and minimum matching constants in geometrical probability
• Large-step Markov chains for the TSP incorporating local search heuristics
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem

This page was built for publication: Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem