An insertion heuristic for the traveling salesman problem adds cities iteratively to an existing tour by replacing one edge with a two-edge path through the new city in the cheapest possible way. In 1977, Rosenkrantz, Stearns, and Lewis asked whether every order of inserting vertices gives a constant-factor approximation algorithm. The authors answer by showing that for some point sets, there is an order that yields tours with length &OHgr; ( log n &slash; loglog n ) times optimum, even if the underlying metric space is the Euclidean plane. Recently, they learned that Y. Azar had independently discovered their result as well as one with performance guaranteed for random insertions. Continuing the pattern of posing new problems, Bafna, Kalyanasundaram, and Pruhs present a number of open questions.