Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

Sepehr Assadi, Sanjeev Khanna, Yang Li +1

In this paper, we introduce a new model for sublinear algorithms called \emph{dynamic sketching}. In this model, the underlying data is partitioned into a large \emph{static} part…