7 citations · 12 across the 22 of their papers we have counts for
4 papers · 1 filter
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
Samuel C. Gutekunst, David P. Williamson
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…
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
Samuel C. Gutekunst, David P. Williamson
The traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization. Several semidefinite programming relaxations have been proposed recently that exploit a…
Tight Bounds for Online Weighted Tree Augmentation
Joseph, Naor, Seeun William Umboh +1
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an -vertex…
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
Samuel C. Gutekunst, David P. Williamson
We consider the integrality gap of the subtour LP relaxation of the Traveling Salesman Problem restricted to circulant instances. De Klerk and Dobre conjectured that the value of t…