Aaron Bernstein

activity

20242026

collaborators

Showing 2024Show all

3 papers · 1 filter

cs.DS2024

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 $n$ -vertex bipartite graph $G = (L, R, E)$ between a set of clients and servers. The goal is to find an assignment of all clients to the ser…

cs.DS2024

Matching Composition and Efficient Weight Reduction in Dynamic Matching

Aaron Bernstein, Jiale Chen, Aditi Dudeja +3

We consider the foundational problem of maintaining a $(1 - ε)$ -approximate maximum weight matching (MWM) in an $n$ -node dynamic graph undergoing edge insertions and deleti…

cs.DS2024

Maximum Flow by Augmenting Paths in $n^{2 + o (1)}$ Time

Aaron Bernstein, Joakim Blikstad, Thatchaphol Saranurak +1

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with $n$ vertices and edge capacities from ${1, \dots, U}$ in $n^{2 + o (1)} lo g U$ time, whi…

Streaming and Communication Complexity of Load-Balancing via Matching Contractors

Matching Composition and Efficient Weight Reduction in Dynamic Matching

Maximum Flow by Augmenting Paths in n2+o(1) Time

Maximum Flow by Augmenting Paths in $n^{2 + o (1)}$ Time