scientific article; zbMATH DE number 3799403
zbMATH Open0506.90059MaRDI QIDQ4744064FDOQ4744064
Authors: Nicos Christofides 
Publication date: 1982
Title of this publication is not available (Why is that?)
surveyheuristicsLagrangian relaxationreviewtravelling salesman problemstate space relaxationinteger programming formulationshortest spanning treeLP-based algorithmsdynamic programming formulation2-matching algorithmsbounds in branching schemesexistence of hamiltonian circuits
Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Dynamic programming (90C39) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Integer programming (90C10)
Cited In (24)
- Heuristics for unequal weight delivery problems with a fixed error guarantee
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- On approximating the minimum independent dominating set
- A cutting plane procedure for the travelling salesman problem on road networks
- Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
- A stochastic dynamic traveling salesman problem with hard time windows
- Set-up saving schemes for printed circuit boards assembly
- On the solutions of stochastic traveling salesman problems
- An approximation algorithm for the TSP
- A note on relatives to the Held and Karp 1-tree problem
- The traveling salesman problem: An overview of exact and approximate algorithms
- Heuristics and bounds for the travelling salesman location problem on the plane
- Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
- Combinatorial optimisation algorithms for a CAD workstation
- Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- The travelling salesman problem with pick-up and delivery
- A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem
- Worst-case analysis of two travelling salesman heuristics
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Analysis of the Held-Karp lower bound for the asymmetric TSP
- A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
- Worst case bounds for the Euclidean matching problem
- Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4744064)
