A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone

DOI10.1016/J.DAM.2010.03.003MaRDI QIDQ708346zbMATH OpenOpenAlexFDO

Authors Dirk Oliver Theis

Publication date 11 October 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0801.1652

zbMATH Keywords

graphical traveling salesman polyhedronHamilton cycle polytopemetric coneSymmetric Traveling Salesman Polytope

Mathematics Subject Classification ID

Paths and cycles (05C38)

Abstract: In this short communication, we observe that the Graphical Traveling Salesman Polyhedron is the intersection of the positive orthant with the Minkowski sum of the Symmetric Traveling Salesman Polytope and the polar of the metric cone. This follows almost trivially from known facts. There are two reasons why we find this observation worth communicating none-the-less: It is very surprising; it helps to understand the relationship between these two important families of polyhedra.

Recommendations

• On the facial structure of symmetric and graphical traveling salesman polyhedra
• On the graphical relaxation of the symmetric traveling salesman polytope
• The Symmetric Traveling Salesman Polytope: New Facets from the Graphical Relaxation
• The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope

Cites work

• scientific article; zbMATH DE number 2064405 (Why is no real title available?)
• scientific article; zbMATH DE number 2084783 (Why is no real title available?)
• On the graphical relaxation of the symmetric traveling salesman polytope
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities

Cited in

(2)

• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• On the facial structure of symmetric and graphical traveling salesman polyhedra

This page was built for publication: A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708346)