scientific article; zbMATH DE number 3646634

MaRDI QIDQ3205014zbMATH OpenFDO

Authors Nicos Christofides

Publication date 1979

zbMATH Keywords

computational complexityheuristicslinear programmingcombinatorial optimizationassignment problemtraveling salesman problemapproximate algorithmsworst-case performancematching problemcomputational aspectsresearch surveybranch-and-bound methodsshortest spanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Boolean programming (90C09)

Cited in

(8)

• Managing tendupatta leaf logistics: an integrated approach
• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• Optimizing over the subtour polytope of the travelling salesman problem
• A restricted Lagrangean approach to the traveling salesman problem
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Two-edge connected spanning subgraphs and polyhedra
• Minimum-weight two-connected spanning networks

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 Q3205014)