Tight bounds for christofides' traveling salesman heuristic
From MaRDI portal
Publication:4180168
DOI10.1007/BF01588956zbMATH Open0396.90098OpenAlexW2006060626MaRDI QIDQ4180168FDOQ4180168
Authors: Gérard Cornuéjols, G. L. Nemhauser 
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) Approximation methods and heuristics in mathematical programming (90C59) Extremal problems in graph theory (05C35) Paths and cycles (05C38)
Cited In (21)
- Special frequency quadrilaterals and an application
- Topological design of ring networks
- On the refinement of bounds of heuristic algorithms for the traveling salesman problem
- Heuristics for unequal weight delivery problems with a fixed error guarantee
- An approximation algorithm for the general routing problem
- A note on heuristics for the traveling salesman problem
- Min-weight double-tree shortcutting for metric TSP: bounding the approximation ratio
- Heuristic methods and applications: A categorized survey
- An extension of Christofides heuristic to the k-person travelling salesman problem
- Minimum-weight two-connected spanning networks
- Discrete extremal problems
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns
- Truly tight bounds for TSP heuristics
- Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
- Worst-case analysis of two travelling salesman heuristics
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
- Approximation algorithms for the Geometric Covering Salesman Problem
- New primal and dual matching heuristics
- SOLVING THE TRAVELING SALESMAN PROBLEM USING EFFICIENT RANDOMIZED PARALLEL APPROXIMATION ALGORITHMS
This page was built for publication: Tight bounds for christofides' traveling salesman heuristic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4180168)
