Greedy

Kind of like MST algorithm, but works with partial tours.

Start with empty partial tour. Add smallest edge that results in a valid partial tour. Repeat until complete tour reached.

Worst-case ratio no worse than $1/2 \log n$, maybe better.

In practice, performs better than MST-based approximation scheme.

Running time?