Traveling salesman polytopes and cut polytopes. Affine reducibility

摘要

Let STSPm be the TSP (traveling salesman polytope) for m cities, and let CUT_n be the cut polytope of the complete n-vertex graph. It is shown that CUT_n is affinely equivalent to some face of the polytope STSP_m with m = (2n-2)(2n-3). On the other hand, STSP_m is shown to be an affine image of some face of the polytope CUT_n with n = (m - 1)~2 + 1.