Publications by Mikhail Kapralov

Related publications (23)

An Optimal Space Lower Bound for Approximating MAX-CUT

We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. At one extreme, there is a trivial 2-approximation for this problem that uses only O(log n) space, namely, count the number of edges and output hal ...

ASSOC COMPUTING MACHINERY2019

Streaming Algorithms for Connectivity Augmentation

Mikhail Kapralov

We study the k-connectivity augmentation problem (k-CAP) in the single-pass streaming model. Given a (k − 1)-edge connected graph G = (V, E) that is stored in memory, and a stream of weighted edges (also called links) L with weights in {0, 1, . . ., W }, t ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

Perfect Matchings in O (n(1.5)) Time in Regular Bipartite Graphs

Mikhail Kapralov

Springer-Verlag2019