Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
From MaRDI portal
Publication:6322741
DOI10.1016/J.ORL.2020.02.011arXiv1907.11669MaRDI QIDQ6322741
David P. Williamson, Samuel C. Gutekunst
Publication date: 26 July 2019
Abstract: De Klerk, Pasechnik, and Sotirov 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 of the subtour elimination linear program. Hence, this semidefinite constraint is implied by a finite set of linear inequality constraints.
This page was built for publication: Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6322741)
