Short Combinatorial Proof that the DFJ Polytope is contained in the MTZ Polytope for the Asymmetric Traveling Salesman Problem

05/17/2018
by   Mark Velednitsky, et al.
0

For the Asymmetric Traveling Salesman Problem (ATSP), it is known that the Dantzig-Fulkerson-Johnson (DFJ) polytope is contained in the Miller-Tucker-Zemlin (MTZ) polytope. The analytic proofs of this fact are quite long. Here, we present a proof which is combinatorial and significantly shorter by relating the formulation to distances in a modified graph.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset