scientific article; zbMATH DE number 3799403

MaRDI QIDQ4744064zbMATH OpenFDO

Authors Nicos Christofides

Publication date 1982

zbMATH Keywords

2-matching algorithmsbounds in branching schemesdynamic programming formulationexistence of hamiltonian circuitsheuristicsinteger programming formulationLagrangian relaxationLP-based algorithmsreviewshortest spanning treestate space relaxationsurveytravelling salesman problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Integer programming (90C10) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Cited in

(24)

• Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns
• A stochastic dynamic traveling salesman problem with hard time windows
• A cutting plane procedure for the travelling salesman problem on road networks
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• Heuristics for unequal weight delivery problems with a fixed error guarantee
• Heuristics and bounds for the travelling salesman location problem on the plane
• An approximation algorithm for the TSP
• A worst-case analysis of two approximate algorithms for the asymmetric travelling salesman problem
• Worst case bounds for the Euclidean matching problem
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• The traveling salesman problem: An overview of exact and approximate algorithms
• Analysis of the Held-Karp lower bound for the asymmetric TSP
• On the solutions of stochastic traveling salesman problems
• Neither the greedy nor the Delaunay triangulation of a planar point set approximates the optimal triangulation
• A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
• Set-up saving schemes for printed circuit boards assembly
• The travelling salesman problem with pick-up and delivery
• Worst-case analysis of some convex hull heuristics for the Euclidean travelling salesman problem
• A note on relatives to the Held and Karp 1-tree problem
• On approximating the minimum independent dominating set
• Combinatorial optimisation algorithms for a CAD workstation
• Worst-case analysis of two travelling salesman heuristics
• Maximum bounded 3-dimensional matching is MAX SNP-complete

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)