7 citations · 12 across the 22 of their papers we have counts for
6 papers · 1 filter
The Circlet Inequalities: A New, Circulant-Based Facet-Defining Inequality for the TSP
Samuel C. Gutekunst, David P. Williamson
Facet-defining inequalities of the symmetric Traveling Salesman Problem (TSP) polytope play a prominent role in both polyhedral TSP research and state-of-the-art TSP solvers. In th…
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…
Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time
Iddo Drori, Anant Kharkar, William R. Sickinger +7
Combinatorial optimization algorithms for graph problems are usually designed afresh for each new problem with careful attention by an expert to the problem structure. In this work…
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…