1 citations · 1 across the 3 of their papers we have counts for
4 papers
Sublinear Algorithms for -Approximate Matching
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime…
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak
In the dynamic linear program (LP) problem, we are given an LP undergoing updates and we need to maintain an approximately optimal solution. Recently, significant attention (e.g.,…
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak +1
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximatio…
Deterministic Rounding of Dynamic Fractional Matchings
Sayan Bhattacharya, Peter Kiss
We present a framework for deterministically rounding a dynamic fractional matching. Applying our framework in a black-box manner on top of existing fractional matching algorithms,…