A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
René van Bevern, Viktoriia A. Slugina
Topics & Concepts
Travelling salesman problemMetric (unit)Christofides algorithmTranslation (biology)AlgorithmBottleneck traveling salesman problemCombinatorial optimizationMathematicsComputer science2-optCombinatoricsTraveling purchaser problemLin–Kernighan heuristicMathematical optimizationExtremal optimizationOptimization problemApproximation algorithmEfficient algorithmVehicle Routing Optimization MethodsComplexity and Algorithms in GraphsGenome Rearrangement Algorithms