The ACO Seminar (2021–2022)

Euclidean Travelling Salesman problem is a NP-Hard problem which actually is solved very frequently in practice using heuristic approaches. A popular approach in this regime is the branch-and-cut method. We will present a proof that even in the average case, the Euclidean TSP exhibits an integrality gap of (1 + \eps) for \eps > 0 when compared to the Help-Karp Linear Programming relaxation augmented by all comb inequalities of bounded size. This implies that a large class of branch-and-cut algorithms, which rely on using comb inequalities as lower bounds take exponential time for the Euclidean TSP, even on "typical" instances -- generated by taking random points in [0,1]^d. This is joint work with Wesley Pedgen, expanding on the result of Frieze and Pedgen (2015).