In the past two years, there has been a lot of exciting progress in this area. In this talk, we review some of the known results, and present somenew results that refine our understanding of the subtour LP. In particular, we resolve a conjecture of Boyd and Carr about the ratio of an optimal 2-matching to the subtour LP bound in the worst case. We also begin a study of the subtour LP bound for the case in which all distances between cities are either 1 or 2. For these instances we show that the worst-caseratio of the value of the optimal tour to the value of the subtour LP is always strictly better than 4/3.
This is based on joint work with Jiawei Qian, Frans Schalekamp and David P. Williamson.