Showing 2026Show all
2 papers · 1 filter
cs.DS2026
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_{…
cs.DS2026
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…