Skip to main content
1 of 3

Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.

Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the nearest-neighbor algorithm (described below) gives a tour that is $n$ times longer than the optimal solution starting $s$?

Starting at $s$, pick the nearest neighbor not visited so far as the next node to visit.