Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP

DOI10.1016/J.ORL.2020.02.011MaRDI QIDQ2183196zbMATH OpenOpenAlexFDO

Authors Samuel C. Gutekunst, David P. Williamson

Publication date 26 May 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.11669

zbMATH Keywords

traveling salesman problemmatrix-tree theoremSDP relaxationsubtour LP

Mathematics Subject Classification ID

Combinatorics (05-XX) Operations research, mathematical programming (90-XX)

Recommendations

• scientific article; zbMATH DE number 1873286
• Constrained spanning trees and the traveling salesman problem
• Semidefinite programming relaxations of the traveling salesman problem and their integrality gaps
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Generalized Subtour Elimination Constraints and Connectivity Constraints

Cites work

• scientific article; zbMATH DE number 1342125 (Why is no real title available?)
• scientific article; zbMATH DE number 1534298 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Graph theory. Foreword by Crispin St. J. A. Nash-Williams.
• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• On the Minimum Number of Spanning Trees ink-Edge-Connected Graphs
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem

Cited in

(1)

• Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP

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 Q2183196)