首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号