research
∙
07/05/2023
Density-Sensitive Algorithms for (Δ+ 1)-Edge Coloring
Vizing's theorem asserts the existence of a (Δ+1)-edge coloring for any ...
share
research
∙
06/20/2023
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
We study dynamic (1-ϵ)-approximate rounding of fractional matchings – a ...
research
∙
04/04/2023
Chasing Positive Bodies
We study the problem of chasing positive bodies in ℓ_1: given a sequence...
research
∙
02/10/2023
Dynamic (1+ε)-Approximate Matching Size in Truly Sublinear Update Time
We show a fully dynamic algorithm for maintaining (1+ϵ)-approximate size...
research
∙
12/01/2022
Sublinear Algorithms for (1.5+ε)-Approximate Matching
We study sublinear time algorithms for estimating the size of maximum ma...
research
∙
10/25/2022
Efficient and Stable Fully Dynamic Facility Location
We consider the classic facility location problem in fully dynamic data ...
research
∙
07/15/2022
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
In the dynamic linear program (LP) problem, we are given an LP undergoin...
research
∙
07/15/2022
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
We present dynamic algorithms with polylogarithmic update time for estim...
research
∙
07/11/2022
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
Designing dynamic algorithms against an adaptive adversary whose perform...
research
∙
04/17/2022
A New Dynamic Algorithm for Densest Subhypergraphs
Computing a dense subgraph is a fundamental problem in graph mining, wit...
research
∙
05/04/2021
Deterministic Rounding of Dynamic Fractional Matchings
We present a framework for deterministically rounding a dynamic fraction...
research
∙
10/30/2020
Online Edge Coloring Algorithms via the Nibble Method
Nearly thirty years ago, Bar-Noy, Motwani and Naor [IPL'92] conjectured ...
research
∙
02/25/2020
Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
In the dynamic minimum set cover problem, a challenge is to minimize the...
research
∙
02/25/2020
An Improved Algorithm for Dynamic Set Cover
We consider the minimum set cover problem in a dynamic setting. Here, we...
research
∙
01/02/2020
Coarse-Grained Complexity for Dynamic Algorithms
To date, the only way to argue polynomial lower bounds for dynamic algor...
research
∙
10/04/2019
Fully Dynamic (Δ+1)-Coloring in Constant Update Time
The problem of (vertex) (Δ+1)-coloring a graph of maximum degree Δ has b...
research
∙
09/25/2019
A New Deterministic Algorithm for Dynamic Set Cover
We present a deterministic dynamic algorithm for maintaining a (1+ϵ)f-ap...
research
∙
02/06/2019
New Amortized Cell-Probe Lower Bounds for Dynamic Problems
We build upon the recent papers by Weinstein and Yu (FOCS'16), Larsen (F...
research
∙
10/08/2018
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
We consider the problem of incremental cycle detection and topological o...
research
∙
05/09/2018
Deterministically Maintaining a (2+ε)-Approximate Minimum Vertex Cover in O(1/ε^2) Amortized Update Time
We consider the problem of maintaining an (approximately) minimum vertex...
research
∙
11/12/2017
Dynamic Algorithms for Graph Coloring
We design fast dynamic algorithms for proper vertex and edge colorings i...
research
∙
04/22/2009