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

DOI10.1016/J.ORL.2020.02.011OpenAlexW3009630668MaRDI QIDQ2183196FDOQ2183196

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

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

zbMATH Keywords

traveling salesman problemmatrix-tree theoremSDP relaxationsubtour LP

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Graph theory. Foreword by Crispin St. J. A. Nash-Williams.
• Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry
• Title not available (Why is that?)
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• Title not available (Why is that?)
• On the Minimum Number of Spanning Trees ink-Edge-Connected Graphs
• 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)