The Euclidean traveling salesman problem is NP-complete

DOI10.1016/0304-3975(77)90012-3MaRDI QIDQ1250163zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Christos Papadimitriou

Publication date 1977

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(77)90012-3

Mathematics Subject Classification ID

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)

• An O(N log N) planar travelling salesman heuristic based on spacefilling curves
• Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
• Euclidean bottleneck bounded-degree spanning tree ratios
• Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters
• The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP
• Strategies for generating well centered tetrahedral meshes on industrial geometries
• Efficiently solving the traveling thief problem using hill climbing and simulated annealing
• The travelling salesman and the PQ-tree
• Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
• The traveling salesman problem with few inner points
• Average optimal cost for the Euclidean TSP in one dimension
• The adjacency relation on the traveling salesman polytope is NP-Complete
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• An new self-organizing maps strategy for solving the traveling salesman problem
• Computing shortest heterochromatic monotone routes
• A branch-and-cut algorithm for the time window assignment vehicle routing problem
• Smoothed analysis of partitioning algorithms for Euclidean functionals
• Dynamic graph conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem
• Constant-factor approximation algorithms for a series of combinatorial routing problems based on the reduction to the asymmetric traveling salesman problem
• GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST
• Degree bounded bottleneck spanning trees in three dimensions
• The traveling salesmanpProblem for lines in the plane
• The Convex-hull-and-k-line Travelling Salesman Problem
• Financial networks with singleton liability priorities
• Partitioning heuristics for two geometric maximization problems
• Euclidean TSP in narrow strips
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Power indices and easier hard problems
• Approximation Algorithms for the Traveling Salesman Problem with Range Condition
• Approximation algorithms for the Geometric Covering Salesman Problem
• Improving the Hopfield model performance when applied to the traveling salesman problem. A divide-and-conquer scheme
• Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic
• Asymptotic expected performance of some TSP heuristics: An empirical evaluation
• Solving the Watchman Route Problem with Heuristic Search
• An ETH-Tight Exact Algorithm for Euclidean TSP
• Priority functions for the approximation of the metric TSP
• The zookeeper route problem
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces
• Cyclic-routing of unmanned aerial vehicles
• 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

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)