12.06.2015

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the underlying paradigms and insights which lead to the recent improvements as well as some inherent obstacles for further progress on those problems.