16 citations · 64 across the 32 of their papers we have counts for
6 papers · 1 filter
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…
Efficient and Stable Fully Dynamic Facility Location
Sayan Bhattacharya, Silvio Lattanzi, Nikos Parotsidis
We consider the classic facility location problem in fully dynamic data streams, where elements can be both inserted and deleted. In this problem, one is interested in maintaining…
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.,…
Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert
Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic grap…
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…
A New Dynamic Algorithm for Densest Subhypergraphs
Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari +1
Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks.…