Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Given a graph G with edge costs and two vertices s and t, the traveling salesman path problem is that of finding a minimum-cost path beginning at s and ending at t that visits every vertex of G at least once. In this talk, we consider the polytope corresponding to a linear programming relaxation for this problem and characterize the set of graphs for which the vertices of this polytope are integral. (Joint work with Alantha Newman)