Comb inequalities for typical Euclidean TSP instances

Wesley Pegden, Anish Sevekari

We prove that even in average case, the Euclidean Traveling Salesman Problem exhibits an integrality gap of $(1+\epsilon )$ for $\epsilon >0$ when the Held-Karp Linear Programming relaxation is au…