paper

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

arXiv:1805.06997 · doi:10.1016/j.orl.2017.04.010

Abstract

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.

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