7 citations · 12 across the 22 of their papers we have counts for
19 papers · 1 filter
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…
Cut-Toggling and Cycle-Toggling for Electrical Flow and Other p-Norm Flows
Monika Henzinger, Billy Jin, Richard Peng +1
We study the problem of finding flows in undirected graphs so as to minimize the weighted -norm of the flow for any . When , the problem is that of finding an electr…
Recursive Random Contraction Revisited
David R. Karger, David P. Williamson
In this note, we revisit the recursive random contraction algorithm of Karger and Stein for finding a minimum cut in a graph. Our revisit is occasioned by a paper of Fox, Panigrahi…
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems
Monika Henzinger, Billy Jin, Richard Peng +1
Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems whose coefficient matrix is the Laplacian matrix of a we…