Nearest Neighbor

Idea: Start at a node. Find closest unvisited node. Visit it. Repeat until finished, then return to start.

Runs fast.

Worst-case ratio of about $1/2 \log n$ (not so good).

Not too bad in practice.

Running time?