Title:
Local Cuts for the Traveling Salesman Abstract: The best known approach to solving large traveling salesman problems was introduced by Dantzig, Fulkerson, and Johnson in 1954, and uses linear programming and cutting planes. I will describe their approach, and a new technique which leverages our ability to efficiently solve small TSPs into a separation algorithm for finding useful cutting planes. |