Back in 2006, I was a post-doc at MPI Saarbruecken in Kurt Mehlhorn's group. At that time, I started working on several TSP variants beginning with my collaboration with Kasia Paluch and Olek Mądry on the symmetric MAX-TSP. The most fascinating of these was not really a TSP variant, but a problem that is solved by a reduction to one - the Shortest Superstring Problem (SSP) in which you look for a shortest string containing a given set of strings as substrings. My fascination was even greater because of the fact that I felt absolutely certain that I had an idea to improve upon the already rather old result of Sweedyk (from 1991) giving 2 1/2-approximation, only somehow I could not quite make it work. The thing was that the same 2 1/2-approximation could be achieved by using a 2/3-approximation algorithm for MAX-ATSP from a paper by Heim Kaplan, Moshe Lewenstein, Nira Shafrir and Maxim Sviridenko, but just using that result as a black-box did not seem right. However, the proof of the 2/3-approximation there was rather complicated so I could not really put my finger on it.
Fast forward 7 years foward, after several unsuccessful attempts to improve upon the 2 1/2 factor, I stumbled upon a beatiful STACS paper again by Kasia Paluch, together with Khaled Elbassioni and Anke van Zuylen, which gives a new 2 1/2-approximation algorithm for MAX-ATSP. (If you have not yet read this paper, do it!) Obviously, I decided to try adapt this paper to my needs and use it to approximate SSP. That attempt failed completely after a rather heavy struggle. However, on the next day after realizing it was not going to work, it turned out the effort was not in vain - I had the right idea all along, only did not completely realize it. This was one of those crazy moments in research where you are obsessively trying to find something, only to find something completely different and unexpected, and equally or even more valuable!
I will not describe the approach here - that would necessarily be rather long, since the paper builds quite heavily on previous results. However, I am going to present this result at SODA 2013 in January. So if you want to learn more about how a 13 years old bound was improved, come to my talk in New Orleans, or even better chat with me over coffee. See you in 3 months!
Marcin