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


Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP
Abstract:De Klerk et al., (2008) give a semidefinite programming constraint for the Traveling Salesman Problem (TSP) based on the matrix-tree theorem. This constraint says that the aggregate weight of all spanning trees in a solution to a TSP relaxation is at least that of a cycle graph. In this note, we show that the semidefinite constraint holds for any weighted 2-edge-connected graph and, in particular, is implied by the subtour elimination constraints.
Keywords:Traveling Salesman Problem  Subtour LP  Matrix-tree theorem  SDP relaxation
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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