Traveling salesman polytopes and cut polytopes. Affine reducibility
Aleksandr Nikolaevich Maksimenko · Discrete Mathematics and Applications · 2013
Let STSP m 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.