7 citations · 12 across the 22 of their papers we have counts for
4 papers · 1 filter
A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
Billy Jin, Nathan Klein, David P. Williamson
A long-standing conjecture for the traveling salesman problem (TSP) states that the integrality gap of the standard linear programming relaxation of the TSP is at most 4/3. Despite…
GILP: An Interactive Tool for Visualizing the Simplex Algorithm
Henry W. Robbins, Samuel C. Gutekunst, David B. Shmoys +1
The Simplex algorithm for solving linear programs-one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century-is an important topic in many a…
The Two-Stripe Symmetric Circulant TSP is in P
Samuel C. Gutekunst, Billy Jin, David P. Williamson
The symmetric circulant TSP is a special case of the traveling salesman problem in which edge costs are symmetric and obey circulant symmetry. Despite the substantial symmetry of t…
Graph Coloring and Semidefinite Rank
Renee Mirka, Devin Smedira, David P. Williamson
This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan \cite{KMS98} give a vector program for which a colo…