A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone |
| |
Authors: | Dirk Oliver Theis |
| |
Affiliation: | Service de Géométrie Combinatoire et Théorie des Groupes, Département de Mathématique, Université Libre de Bruxelles, Brussels, Belgium |
| |
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 nonetheless two reasons why we find this observation worth communicating: It is very surprising; it helps us understand the relationship between these two important families of polyhedra. |
| |
Keywords: | Symmetric Traveling Salesman Polytope Hamilton cycle polytope Graphical traveling salesman polyhedron Metric cone |
本文献已被 ScienceDirect 等数据库收录! |