7 citations · 12 across the 22 of their papers we have counts for
26 papers
A Simplified Analysis of the Good-Bad -Approximation Algorithm for Some Minimum-Cost Graph Problems
Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade
In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected…
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs
Emmett Breen, Renee Mirka, Zichen Wang +1
This paper revisits the 2-approximation algorithm for -MST presented by Garg in light of a recent paper of Paul et al.. In the -MST problem, the goal is to return a tree span…
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…