13 citations · 26 across the 10 of their papers we have counts for
3 papers · 1 filter
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…
Online Nash Social Welfare Maximization with Predictions
Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh +1
We consider the problem of allocating a set of divisible goods to agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provi…
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…