Improved integrality gap upper bounds for traveling salesperson problems with distances one and two

We prove these bounds by providing local search algorithms that, in polynomial time, find 2-matchings with few components in the support of the solution. We show that the run times of our algorithms cannot be considerably improved under standard complexity-theoretic assumptions: we show that finding improved TSP solutions via local search is intractable for edge change parameterized by the size of the neighborhoods even for instances with distances one and two; this strengthens a result of Dániel Marx.