The Approximation Ratio of the Greedy Algorithm for the Metric Traveling Salesman Problem

Judith Brecklinghaus, Stefan Hougardy

We prove that the approximation ratio of the greedy algorithm for the metric Traveling Salesman Problem is $\Theta (\log n)$. Moreover, we prove that the same result also holds for graph…