mlsanityData to 14 Oct 2026

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

arXiv 1412.7366 ↗First posted 23 Dec 2014cs.DM cs.DS math.COcited by 2

Not on the map. Why?

Abstract (arXiv)

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 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(log n).

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). First posted on arXiv 23 Dec 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025RedAHD: Reduction-Based End-to-End Automatic Heuristic Design with Large Language Modelscited by 4
  2. 2026MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Designcited by 0