3 citations · 5 across the 10 of their papers we have counts for
5 papers · 1 filter
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard, Nicole Wein
Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with edges requires $m^{2-o(1)…
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg +2
Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and…
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
Aaron Berger, William Kuszmaul, Adam Polak +2
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of workers and a multiset of tasks,…
Lower Bounds for Dynamic Distributed Task Allocation
Hsin-Hao Su, Nicole Wein
We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the…
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph subject to edge insertions and deletions and a source vertex , and the goal is to…