research
∙
07/28/2023
Dynamic algorithms for k-center on graphs
In this paper we give the first efficient algorithms for the k-center pr...
share
research
∙
07/19/2023
On Dynamic Graph Algorithms with Predictions
We study dynamic algorithms in the model of algorithms with predictions....
research
∙
07/18/2023
Fast 2-Approximate All-Pairs Shortest Paths
In this paper, we revisit the classic approximate All-Pairs Shortest Pat...
research
∙
03/10/2023
Bootstrapping Dynamic Distance Oracles
Designing approximate all-pairs distance oracles in the fully dynamic se...
research
∙
11/08/2022
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
We provide the first deterministic data structure that given a weighted ...
research
∙
11/02/2022
New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
We provide new tradeoffs between approximation and running time for the ...
research
∙
09/08/2022
Epic Fail: Emulators can tolerate polynomially many edge faults for free
A t-emulator of a graph G is a graph H that approximates its pairwise sh...
research
∙
11/05/2021
Fast Deterministic Fully Dynamic Distance Approximation
In this paper, we develop deterministic fully dynamic algorithms for com...
research
∙
09/16/2021
Vertex Fault-Tolerant Emulators
A k-spanner of a graph G is a sparse subgraph that preserves its shortes...
research
∙
07/14/2021
Online Allocation and Display Ads Optimization with Surplus Supply
In this work, we study a scenario where a publisher seeks to maximize it...
research
∙
09/17/2020
Near-Optimal Decremental Approximate Multi-Source Shortest Paths
We provide new algorithms for maintaining approximate distances in a wei...
research
∙
03/02/2020
Massively Parallel Algorithms for Distance Approximation and Spanners
Over the past decade, there has been increasing interest in distributed/...
research
∙
11/17/2019
Sparse Hopsets in Congested Clique
We give the first Congested Clique algorithm that computes a sparse hops...
research
∙
05/17/2019
Lasserre Integrality Gaps for Graph Spanners and Related Problems
There has been significant recent progress on algorithms for approximati...
research
∙
10/21/2018
