The approximation ratio of the greedy algorithm for the metric traveling salesman problem

DOI10.1016/J.ORL.2015.02.009MaRDI QIDQ1785355zbMATH OpenOpenAlexFDO

Authors Judith Brecklinghaus, Stefan Hougardy

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.7366

zbMATH Keywords

approximation algorithmClarke-Wright savings heuristicgreedy algorithmtraveling salesman problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)

Abstract: We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is $Theta(logn)$. Moreover, we prove that the same result also holds for graphic, Euclidean, and rectilinear instances of the Traveling Salesman Problem. Finally we show that the approximation ratio of the Clarke-Wright savings heuristic for the metric Traveling Salesman Problem is $Theta(logn)$.

Recommendations

• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• Improved deterministic approximation algorithms for max TSP
• \(\frac{13}{9}\)-approximation for graphic TSP
• Algorithms – ESA 2005
• \(\frac {13}{9}\)-approximation for graphic TSP

Cites work

• scientific article; zbMATH DE number 3630482 (Why is no real title available?)
• On the nearest neighbor rule for the metric traveling salesman problem
• On the nearest neighbor rule for the traveling salesman problem
• Reducibility among combinatorial problems
• The traveling salesman. Computational solutions for RSP applications
• Worst-case analysis of two travelling salesman heuristics

Cited in

(10)

• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• The approximation ratio of the 2-Opt heuristic for the metric traveling salesman problem
• scientific article; zbMATH DE number 4019111 (Why is no real title available?)
• A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique
• scientific article; zbMATH DE number 1534500 (Why is no real title available?)
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• The greedy algorithm for the symmetric TSP
• scientific article; zbMATH DE number 7651222 (Why is no real title available?)
• The bright side of simple heuristics for the TSP
• Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: The approximation ratio of the greedy algorithm for the metric traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785355)