The Euclidean traveling salesman problem is NP-complete
From MaRDI portal
Publication:1250163
DOI10.1016/0304-3975(77)90012-3zbMath0386.90057DBLPjournals/tcs/Papadimitriou77OpenAlexW2055569927WikidataQ56067404 ScholiaQ56067404MaRDI QIDQ1250163
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
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Enumeration in graph theory (05C30) Applications of graph theory to circuits and networks (94C15) Combinatorial aspects of packing and covering (05B40)
Related Items (only showing first 100 items - show all)
Quantum annealing for combinatorial clustering ⋮ Faster algorithms for orienteering and \(k\)-TSP ⋮ Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems ⋮ The convex-hull-and-line traveling salesman problem: A solvable case ⋮ A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring ⋮ The incorporation of an efficient initialization method and parameter adaptation using self-organizing maps to solve the TSP ⋮ A simplified NP-complete MAXSAT problem ⋮ On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem ⋮ Linear time approximation schemes for vehicle scheduling problems ⋮ Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic ⋮ Approximation algorithms for the Geometric Covering Salesman Problem ⋮ On a new edge function on complete weighted graphs and its application for locating Hamiltonian cycles of small weight ⋮ The Convex-hull-and-k-line Travelling Salesman Problem ⋮ The hybrid electric vehicle-traveling salesman problem ⋮ A survey on single crane scheduling in automated storage/retrieval systems ⋮ Special cases of travelling salesman problems and heuristics ⋮ Approximability of the minimum-weight \(k\)-size cycle cover problem ⋮ Ordered spatial sampling by means of the traveling salesman problem ⋮ Optimum watchman routes ⋮ Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem ⋮ A branch-and-cut algorithm for the time window assignment vehicle routing problem ⋮ Alternating paths and cycles of minimum length ⋮ Quantizers ad the worst case Euclidean traveling salesman problem ⋮ A PTAS for MIN-\(k\)-SCCP in Euclidean space of arbitrary fixed dimension ⋮ Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension ⋮ An exploration of combinatorial testing-based approaches to fault localization for explainable AI ⋮ The simultaneous semi-random model for TSP ⋮ Reduction techniques providing initial groupings for Euclidean traveling salesman patching algorithms ⋮ Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon ⋮ Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces ⋮ Graph-based point drift: graph centrality on the registration of point-sets ⋮ The traveling salesman problem on grids with forbidden neighborhoods ⋮ On global integer extrema of real-valued box-constrained multivariate quadratic functions ⋮ On the complexity of path problems in properly colored directed graphs ⋮ A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods ⋮ Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries ⋮ An adaptive insertion algorithm for the single-vehicle dial-a-ride problem with narrow time windows ⋮ Strategies for parallel unaware cleaners ⋮ Cyclic-routing of unmanned aerial vehicles ⋮ Probabilistic analysis of some Euclidean clustering problems ⋮ Watchman tours for polygons with holes ⋮ 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 ⋮ Improving the Hopfield model performance when applied to the traveling salesman problem. A divide-and-conquer scheme ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals ⋮ The Shortest Separating Cycle Problem ⋮ On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem. I ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ An O(N log N) planar travelling salesman heuristic based on spacefilling curves ⋮ Priority functions for the approximation of the metric TSP ⋮ Watchman routes for lines and line segments ⋮ Equilibria, fixed points, and complexity classes ⋮ Optimizing flight trajectory of UAV for efficient data collection in wireless sensor networks ⋮ Boundary properties of the satisfiability problems ⋮ A cloud based job sequencing with sequence-dependent setup for sheet metal manufacturing ⋮ Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches ⋮ FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS ⋮ The Length of Elements in Free Solvable Groups ⋮ Application of imperialist competitive algorithm on solving the traveling salesman problem ⋮ 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 ⋮ Watchman routes under limited visibility ⋮ Travelling salesman problem in tissue P systems with costs ⋮ The zookeeper route problem ⋮ Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension ⋮ Hard to solve instances of the Euclidean traveling salesman problem ⋮ A comparative analysis of several asymmetric traveling salesman problem formulations ⋮ Traveling worker assembly line (re)balancing problem: model, reduction techniques, and real case studies ⋮ Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles ⋮ The \(x\)-and-\(y\)-axes travelling salesman problem ⋮ Exact algorithms for the Hamiltonian cycle problem in planar graphs ⋮ Cooperative TSP ⋮ Minimum weight connectivity augmentation for planar straight-line graphs ⋮ An new self-organizing maps strategy for solving the traveling salesman problem ⋮ Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks ⋮ Path optimization with limited sensing ability ⋮ Fractal dimension and lower bounds for geometric problems ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Computing shortest heterochromatic monotone routes ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ Efficient approximation of the metric CVRP in spaces of fixed doubling dimension ⋮ Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension ⋮ Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency ⋮ Testing the necklace condition for shortest tours and optimal factors in the plane ⋮ The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme ⋮ Synchronized pickup and delivery problems with connecting FIFO stack ⋮ NP-completeness of the Hamming salesman problem ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ On the r,s-SAT satisfiability problem and a conjecture of Tovey ⋮ Asymptotic expected performance of some TSP heuristics: An empirical evaluation ⋮ Traveling salesman games with the Monge property ⋮ Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio ⋮ Efficiently solving the traveling thief problem using hill climbing and simulated annealing ⋮ A simplified NP-complete satisfiability problem ⋮ Partitioning heuristics for two geometric maximization problems ⋮ The traveling salesman problem with few inner points ⋮ Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation ⋮ Optimal search with positive switch cost is NP-hard ⋮ The traveling salesmanpProblem for lines in the plane ⋮ Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
Cites Work
This page was built for publication: The Euclidean traveling salesman problem is NP-complete
