Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem

Thomas Watson

We study the lift-and-project procedures of Lov{á}sz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with tri…