Complexity of the V-opt heuristic Traveling Salesman algorithm
According to the original 1973 paper, the Lin-Kernighan algorithm 


  ...produces optimum results with high frequency, in running times
  that grow about as $n^2$.


The iterated Lin-Kernighan variant, proposed by Johnson in 1990, offers an observed improvement to $O(n^{1.25})$; an experimental treatment of this and many other local optimization TSP heuristics can be found here.