Worst-case analysis of a new heuristic for the travelling salesman problem

DOI10.1007/S43069-021-00101-ZzbMATH Open1489.90150OpenAlexW2117226423MaRDI QIDQ2120141FDOQ2120141

Authors: Nicos Christofides 

Publication date: 31 March 2022

Published in: SN Operations Research Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s43069-021-00101-z

Recommendations

• An approximation algorithm for the TSP
• The travelling salesman problem: selected algorithms and heuristics†
• The traveling salesman problem. Approximate algorithms
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• scientific article; zbMATH DE number 795217

zbMATH Keywords

worst-case analysisshortest spanning treetriangularity condition

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Title not available (Why is that?)
• The Loading Problem
• The Complexity of Near-Optimal Graph Coloring
• The Shortest Hamiltonian Chain of a Graph

Cited In (81)

• Heuristic Hungarian method to solve the traveling salesman problem
• Move schedules: fast persistence computations in coarse dynamic settings
• Lower bounds of functions on finite abelian groups
• Improved approximation algorithms for multidepot capacitated vehicle routing
• The heterogeneous rooted tree cover problem
• The Approximation Ratio of the k-Opt Heuristic for the Euclidean Traveling Salesman Problem
• A one pass streaming algorithm for finding Euler tours
• SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decomposition
• Approximation algorithms with constant factors for a series of asymmetric routing problems
• Ordered scheduling in control-flow distributed transactional memory
• On minimum spanning trees for random Euclidean bipartite graphs
• Time complexity of the analyst's traveling salesman algorithm
• Heuristic sequencing methods for time optimal tracking of nested, open and closed paths
• Spanning closed walks and TSP in 3-connected planar graphs
• An improved approximation guarantee for prize-collecting TSP
• An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs
• Approximation algorithms for solving the heterogeneous Chinese postman problem
• The power of recourse for online MST and TSP
• A greedy algorithm for finding maximum spanning trees in infinite graphs
• Simple algorithms for gilmore-gomory's traveling salesman and related problems
• Tour recommendation for groups
• The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic
• DNA origami and the complexity of Eulerian circuits with turning costs
• In memoriam: Nicos Christofides (1942--2019)
• A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring
• Online covering salesman problem
• Scheduling ships movements within a canal harbor
• An approximation algorithm for the TSP
• Approximation Algorithms for Barrier Sweep Coverage
• Worst-Case Growth Rates of Some Classical Problems of Combinatorial Optimization
• Title not available (Why is that?)
• A minimum spanning tree based heuristic for the travelling salesman tour
• Continuous relaxations for the traveling salesman problem
• Metric violation distance: hardness and approximation
• The traveling salesman problem: An overview of exact and approximate algorithms
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Heuristics and bounds for the travelling salesman location problem on the plane
• Novel concave hull-based heuristic algorithm for TSP
• From symmetry to asymmetry: generalizing TSP approximations by parametrization
• One-to-many-to-one single vehicle pickup and delivery problems
• On the approximability of the maximum common subgraph problem
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Title not available (Why is that?)
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Weighted amplifiers and inapproximability results for travelling salesman problem
• TSP tours in cubic graphs: beyond 4/3
• Title not available (Why is that?)
• Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems
• Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
• Routing under uncertainty: the \textit{a priori} traveling repairman problem
• On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices
• On the Hardness of Reoptimization
• Matroid-based TSP rounding for half-integral solutions
• The simultaneous semi-random model for TSP
• Minimizing data collection latency with unmanned aerial vehicle in wireless sensor networks
• Optimizing Read Reversals for Sequence Compression
• Implementation analysis of efficient heuristic algorithms for the traveling salesman problem
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• A partitioning column approach for solving LED sorter manipulator path planning problems
• On the metric \(s\)-\(t\) path traveling salesman problem
• On global integer extrema of real-valued box-constrained multivariate quadratic functions
• Algorithms for Euclidean degree bounded spanning tree problems
• An approximation algorithm for a general class of parametric optimization problems
• Improving TSP tours using dynamic programming over tree decompositions
• The travelling salesman and the PQ-tree
• Trajectory optimization of laser-charged UAV to minimize the average age of information for wireless rechargeable sensor network
• Strategies for generating well centered tetrahedral meshes on industrial geometries
• Fat computational complexity and heuristic design for the TSP
• Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• Title not available (Why is that?)
• \(\frac{13}{9}\)-approximation for graphic TSP
• Computing in combinatorial optimization
• Approximating minimum-cost connected \(T\)-joins
• An approximation algorithm for the clustered path travelling salesman problem
• Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder)
• The traveling-salesman problem
• Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems
• Maximizing energy efficiency for charger scheduling of WRSNs
• The parameterized complexity of local search for TSP, more refined
• Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications

This page was built for publication: Worst-case analysis of a new heuristic for the travelling salesman problem

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