Robust Sparsification for Matroid Intersection with Applications

Matroid intersection is a classical optimization problem where, given two matroids over the same ground set, the goal is to find the largest common independent set. In this paper, we show that there exists a certain "sparsifer": a subset of elements, of size O(|S opt | • 1/ε), where S opt denotes the optimal solution, that is guaranteed to contain a 3/2 + ε approximation, while guaranteeing certain robustness properties. We call such a small subset a Density Constrained Subset (DCS), which is inspired by the Edge-Degree Constrained Subgraph (EDCS) [Bernstein and Stein, 2015], originally designed for the maximum cardinality matching problem in a graph. Our proof is constructive and hinges on a greedy decomposition of matroids, which we call the density-based decomposition. We show that this sparsifier has certain robustness properties that can be used in one-way communication and random-order streaming models.

Specifically, we use the DCS to design a one-way communication protocol for matroid intersection and obtain a 3/2 + ε approximation, using a message of size O(|S opt | • 1/ε). This matches the best achievable ratio for the one-way communication bipartite matching [Goel, Kapralov, and Khanna, 2012].

Moreover, the DCS can be used to design a streaming algorithm in the random-order streaming model requiring the space of O(|S opt | • poly(log(n), 1/ε)), where n is the size of the stream (the ground set of the matroids). Our algorithm guarantees a 3/2 + ε approximation in expectation and, when the size of S opt is not too small, with high probability. Prior to our work, the best approximation ratio of a streaming algorithm in the random-order streaming model was an expected 2 -δ for some small constant δ > 0 [Guruganesh and Singla, 2017].