research
∙
07/17/2023
Fully Dynamic Matching: (2-√(2))-Approximation in Polylog Update Time
We study maximum matchings in fully dynamic graphs, which are graphs tha...
share
research
∙
01/13/2023
Sublinear Algorithms for TSP via Path Covers
We study sublinear time algorithms for the traveling salesman problem (T...
research
∙
11/29/2022
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Sublinear time algorithms for approximating maximum matching size have l...
research
∙
06/27/2022
Beating Greedy Matching in Sublinear Time
We study sublinear time algorithms for estimating the size of maximum ma...
research
∙
05/18/2022
Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
Motivated by applications in the gig economy, we study approximation alg...
research
∙
07/02/2021
Sequential importance sampling for estimating expectations over the space of perfect matchings
This paper makes three contributions to estimating the number of perfect...
research
∙
06/18/2021
Beating the Folklore Algorithm for Dynamic Matching
The maximum matching problem in dynamic graphs subject to edge updates (...
research
∙
12/01/2019