9 papers
Distributed Load Balancing on Unrelated Machines
Aaron Bernstein, Anupam Gupta, Zhaozi Wang
We study the well-known load balancing problem in the distributed CONGEST model of computation. We consider the unrelated machines setting, where each job specifies a size $s_{…
Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
Vikrant Ashvinkumar, Aaron Bernstein, Maximilian Probst Gutenberg +1
We present parallel algorithms for computing single-source reachability and shortest paths on directed -vertex -edge graphs using near-linear work and $o(\sqrt…
Reviving Thorup's Shortcut Conjecture
Aaron Bernstein, Henry Fleischmann, Maximilian Probst Gutenberg +7
We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph…
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer +2
We establish the first update-time separation between dynamic algorithms against oblivious adversaries and those against adaptive adversaries in natural dynamic graph problems, bas…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, Peter Kiss +1
We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an -vertex graph in amortized update time. This breaks the long-standi…
Streaming and Communication Complexity of Load-Balancing via Matching Contractors
Sepehr Assadi, Aaron Bernstein, Zachary Langley +2
In the load-balancing problem, we have an -vertex bipartite graph between a set of clients and servers. The goal is to find an assignment of all clients to the ser…
Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Jiale Chen, Aditi Dudeja +3
We consider the foundational problem of maintaining a -approximate maximum weight matching (MWM) in an -node dynamic graph undergoing edge insertions and deleti…
Maximum Flow by Augmenting Paths in Time
Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1
We present a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time, whi…