A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone
From MaRDI portal
Publication:708346
DOI10.1016/J.DAM.2010.03.003zbMATH Open1230.05183arXiv0801.1652OpenAlexW2056368398MaRDI QIDQ708346FDOQ708346
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
graphical traveling salesman polyhedronHamilton cycle polytopemetric coneSymmetric Traveling Salesman Polytope
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- 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)
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)
