3 citations · 5 across the 5 of their papers we have counts for
3 papers · 1 filter
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.,…
Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in Amortized Update Time
Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletion…
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
Sayan Bhattacharya, Monika Henzinger, Giuseppe F. Italiano
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph , with and $|…