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.003zbMATH Open1230.05183arXiv0801.1652OpenAlexW2056368398MaRDI QIDQ708346FDOQ708346

Authors: Dirk Oliver Theis 

Publication date: 11 October 2010

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

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.

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

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

zbMATH Keywords

graphical traveling salesman polyhedronHamilton cycle polytopemetric coneSymmetric Traveling Salesman Polytope

Mathematics Subject Classification ID

Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• Title not available (Why is that?)
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation
• On the graphical relaxation of the symmetric traveling salesman polytope

Cited In (2)

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

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)