7 citations · 12 across the 22 of their papers we have counts for
Showing 2019 · cs.DSShow all
3 papers · 2 filters
cs.DS2019
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…
cs.DS2019
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…
cs.DS2019
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…