7 citations · 12 across the 22 of their papers we have counts for
4 papers · 2 filters
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…
Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
Billy Jin, David P. Williamson
In this paper, we consider the online vertex-weighted bipartite matching problem in the random arrival model. We consider the generalization of the RANKING algorithm for this probl…
Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing
Alice Paul, David P. Williamson
In this note, we consider the capacitated facility location problem when the transportation costs of the instance satisfy the Monge property. We show that a straightforward dynamic…