Worst-case analysis of a new heuristic for the traveling salesman problem

Christofides, N. (1976). Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388.

Type

Report

Intellectual base

Grey literature

Year

1976

Link

https://apps.dtic.mil/sti/citations/ADA025602

Cited from

operations_research

Cited by

2 citations across 2 artifacts.

Primes

• Scheduling
  • Not limited to time slots: generalized scheduling includes sequencing decisions (what order, even without timestamps), matching (which resource to which task — bipartite matching or assignment), and routing (which path for a job in a flow-shop — a generalization related to the traveling salesman problem, where Christofides (1976) showed a 1.5-approximation for metric TSP).

Domain-specific

• Approximation Algorithm
  • Metric traveling salesperson. Christofides' algorithm combines a minimum spanning tree, a minimum-weight perfect matching on odd-degree vertices, an Euler tour, and shortcutting to obtain a tour no more than \(3/2\) times optimum under metric assumptions.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:afc4afe5b2b7 · see in the full table