IKCEST

Operations Research Letters | Vol.45, Issue.4 | | Pages

Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem

Mark Velednitsky

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.

Original Text (This is the original text for your reference.)

Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem

+More

Keywords

graph dantzigfulkersonjohnson dfj polytope asymmetric traveling salesman problem millertuckerzemlin mtz

Cite this article

APA

MLA

Chicago

Mark Velednitsky,.Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the Asymmetric Traveling Salesman Problem. 45 (4),.

Disclaimer: The translated content is provided by third-party translation service providers, and IKCEST shall not assume any responsibility for the accuracy and legality of the content.