Tight bounds for christofides' traveling salesman heuristic
From MaRDI portal
Publication:4180168
DOI10.1007/BF01588956zbMath0396.90098OpenAlexW2006060626MaRDI QIDQ4180168
Cornuéjols, Gérard, Nemhauser, George I.
Publication date: 1978
Published in: Mathematical Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01588956
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Approximation methods and heuristics in mathematical programming (90C59) Paths and cycles (05C38)
Related Items
Approximation algorithms for the Geometric Covering Salesman Problem, New primal and dual matching heuristics, Heuristics for unequal weight delivery problems with a fixed error guarantee, Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation, Truly tight bounds for TSP heuristics, Discrete extremal problems, Analysis of Christofides' heuristic: some paths are more difficult than cycles, Special Frequency Quadrilaterals and an Application, An approximation algorithm for the general routing problem, Polynomial approximation algorithms with performance guarantees: an introduction-by-example, Minimum-weight two-connected spanning networks, A note on heuristics for the traveling salesman problem, Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns, Heuristic methods and applications: A categorized survey, Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio, An extension of Christofides heuristic to the k-person travelling salesman problem, Worst-case analysis of two travelling salesman heuristics, SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS, A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems, On the refinement of bounds of heuristic algorithms for the traveling salesman problem, Topological design of ring networks
