7 citations · 12 across the 22 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.DS2017
The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem
Samuel C. Gutekunst, David P. Williamson
We study a semidefinite programming relaxation of the traveling salesman problem introduced by de Klerk, Pasechnik, and Sotirov [8] and show that their relaxation has an unbounded…
cs.DS2017
Online Constrained Forest and Prize-Collecting Network Design
Jiawei Qian, Seeun William Umboh, David P. Williamson
In this paper, we study a very general type of online network design problem, and generalize two different previous algorithms, one for an online network design problem due to Berm…