The Euclidean traveling salesman problem is NP-complete

DOI10.1016/0304-3975(77)90012-3zbMATH Open0386.90057DBLPjournals/tcs/Papadimitriou77OpenAlexW2055569927WikidataQ56067404 ScholiaQ56067404MaRDI QIDQ1250163FDOQ1250163

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

• Title not available (Why is that?)
• A Dynamic Programming Approach to Sequencing Problems
• Title not available (Why is that?)
• 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)

• 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 the complexity of path problems in properly colored directed graphs
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A simplified NP-complete satisfiability problem
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
• A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring
• Quantizers ad the worst case Euclidean traveling salesman problem
• Reduction techniques providing initial groupings for Euclidean traveling salesman patching algorithms
• Cooperative TSP
• Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
• A simplified NP-complete MAXSAT problem
• 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
• 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
• Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon
• Approximation algorithms for multi-robot patrol-scheduling with min-max latency
• On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight
• Watchman routes for lines and line segments
• Hard to solve instances of the Euclidean traveling salesman problem
• Equilibria, fixed points, and complexity classes
• Linear time approximation schemes for vehicle scheduling problems
• On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem. I
• A survey on single crane scheduling in automated storage/retrieval systems
• The hybrid electric vehicle-traveling salesman problem
• 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
• The convex-hull-and-line traveling salesman problem: A solvable case
• Boundary properties of the satisfiability problems
• Strategies for parallel unaware cleaners
• Approximability of the minimum-weight \(k\)-size cycle cover problem
• Ordered spatial sampling by means of the traveling salesman problem
• An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows
• Probabilistic analysis of some Euclidean clustering problems
• Alternating paths and cycles of minimum length
• NP-completeness of the Hamming salesman problem
• The Length of Elements in Free Solvable Groups
• Special cases of travelling salesman problems and heuristics
• Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension
• An O(N log N) planar travelling salesman heuristic based on spacefilling curves
• The travelling salesman and the PQ-tree
• The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Efficiently solving the traveling thief problem using hill climbing and simulated annealing
• The traveling salesman problem with few inner points
• Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension
• 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
• The Convex-hull-and-k-line Travelling Salesman Problem
• Power indices and easier hard problems
• Partitioning heuristics for two geometric maximization problems
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Approximation algorithms for the Geometric Covering Salesman Problem
• An ETH-Tight Exact Algorithm for Euclidean TSP
• Asymptotic expected performance of some TSP heuristics: An empirical evaluation
• 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
• Travelling salesman problem in tissue P systems with costs
• The shortest separating cycle problem
• Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation
• 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
• On computing optimal linear diagrams
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• Approximation ineffectiveness of a tour-untangling heuristic
• Application of imperialist competitive algorithm on solving the traveling salesman problem
• Quantum annealing for combinatorial clustering
• Faster algorithms for orienteering and \(k\)-TSP
• 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
• Financial networks with singleton liability priorities
• A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods
• Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles
• 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
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• Temporal Traveling Salesman Problem – in a Logic- and Graph Theory-Based Depiction
• Problem-Specific Branch-and-Bound Algorithms for the Precedence Constrained Generalized Traveling Salesman Problem
• Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches
• The \(x\)-and-\(y\)-axes travelling salesman problem
• Observation routes and external watchman routes
• Complexity of inventory routing problems when routing is easy
• The simultaneous semi-random model for TSP
• Fractal dimension and lower bounds for geometric problems
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• The traveling salesman problem on grids with forbidden neighborhoods
• Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies
• Constant-factor approximation for TSP with disks
• Observation routes and external watchman routes

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)