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

DOI10.1016/j.orl.2020.02.011OpenAlexW3009630668MaRDI QIDQ2183196

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

SDP relaxationtraveling salesman problemmatrix-tree theoremsubtour LP

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• On the Minimum Number of Spanning Trees ink-Edge-Connected Graphs
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees

This page was built for publication: Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP