The Euclidean traveling salesman problem is NP-complete

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Applications of graph theory to circuits and networks (94C15) Combinatorial aspects of packing and covering (05B40)

Cites work

scientific article; zbMATH DE number 3571502 (Why is no real title available?)
scientific article; zbMATH DE number 3588048 (Why is no real title available?)
A Dynamic Programming Approach to Sequencing Problems
An Effective Heuristic Algorithm for the Traveling-Salesman Problem
On the Complexity of Local Search for the Traveling Salesman Problem

Cited in

(only showing first 100 items - show all)

Travelling salesman problem in tissue P systems with costs
A novel algorithm for construction of the shortest path between a finite set of nonintersecting contours on the plane
Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation
The shortest separating cycle problem
A cloud based job sequencing with sequence-dependent setup for sheet metal manufacturing
Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks
Watchman routes under limited visibility
Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems
Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension
On computing optimal linear diagrams
On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
Application of imperialist competitive algorithm on solving the traveling salesman problem
On the complexity of path problems in properly colored directed graphs
Approximation ineffectiveness of a tour-untangling heuristic
A comparative analysis of several asymmetric traveling salesman problem formulations
A simplified NP-complete satisfiability problem
A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring
Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
Quantum annealing for combinatorial clustering
Quantizers ad the worst case Euclidean traveling salesman problem
Reduction techniques providing initial groupings for Euclidean traveling salesman patching algorithms
Cooperative TSP
Faster algorithms for orienteering and \(k\)-TSP
Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods
A simplified NP-complete MAXSAT problem
Fault-tolerant families of production plans: mathematical model, computational complexity, and branch-and-bound algorithms
Reliable production process design problem: compact MILP model and ALNS-based primal heuristic
Lower bounds of functions on finite abelian groups
Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles
Financial networks with singleton liability priorities
On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
Optimum watchman routes
Traveling salesman games with the Monge property
Optimal search with positive switch cost is NP-hard
Watchman tours for polygons with holes
Learn global and optimize local: a data-driven methodology for last-mile routing
Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph
Approximability of the problem about a minimum-weight cycle cover of a graph
Path optimization with limited sensing ability
The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon
Temporal Traveling Salesman Problem – in a Logic- and Graph Theory-Based Depiction
Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches
Approximation algorithms for multi-robot patrol-scheduling with min-max latency
The \(x\)-and-\(y\)-axes travelling salesman problem
Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem
Observation routes and external watchman routes
On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight
Complexity of inventory routing problems when routing is easy
Fractal dimension and lower bounds for geometric problems
Watchman routes for lines and line segments
Equilibria, fixed points, and complexity classes
Hard to solve instances of the Euclidean traveling salesman problem
The traveling salesman problem on grids with forbidden neighborhoods
Linear time approximation schemes for vehicle scheduling problems
The simultaneous semi-random model for TSP
Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies
FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
A survey on single crane scheduling in automated storage/retrieval systems
The hybrid electric vehicle-traveling salesman problem
On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem. I
Constant-factor approximation for TSP with disks
On the r,s-SAT satisfiability problem and a conjecture of Tovey
Testing the necklace condition for shortest tours and optimal factors in the plane
SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decomposition
Observation routes and external watchman routes
The convex-hull-and-line traveling salesman problem: A solvable case
An improved upper bound for the universal TSP on the grid
An exploration of combinatorial testing-based approaches to fault localization for explainable AI
Strategies for parallel unaware cleaners
Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
Approximability of the minimum-weight \(k\)-size cycle cover problem
Ordered spatial sampling by means of the traveling salesman problem
Boundary properties of the satisfiability problems
Minimum weight connectivity augmentation for planar straight-line graphs
An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows
The bright side of simple heuristics for the TSP
FPT-algorithms for minimum-bends tours
Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
Probabilistic analysis of some Euclidean clustering problems
Optimal transport methods for combinatorial optimization over two random point sets
Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP
Approximation algorithms with constant factors for a series of asymmetric routing problems
Efficient hybrid Bayesian optimization algorithm with adaptive expected improvement acquisition function
Approximating minimum \(k\)-tree cover of a connected graph inspired by the multi-ferry routing in delay tolerant networks
The simultaneous semi-random model for TSP
Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks
Synchronized pickup and delivery problems with connecting FIFO stack
Alternating paths and cycles of minimum length
Graph-based point drift: graph centrality on the registration of point-sets
Travelling on graphs with small highway dimension
NP-completeness of the Hamming salesman problem
Time complexity of the analyst's traveling salesman algorithm
The Length of Elements in Free Solvable Groups
A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension
Special cases of travelling salesman problems and heuristics
Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem
On global integer extrema of real-valued box-constrained multivariate quadratic functions

This page was built for publication: The Euclidean traveling salesman problem is NP-complete

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