Small Space Stream Summary for Matroid Center

Understand

In the matroid center problem, which generalizes the $k$-center problem, we need to pick a set of centers that is an independent set of a matroid with rank $r$.

• We study this problem in streaming, where elements of the ground set arrive in the stream.
• We first show that any randomized one-pass streaming algorithm that computes a better than $\Delta$-approximation for partition-matroid center must use $\Omega(r^2)$ bits of space, where $\Delta$ is the aspect ratio of the metric and can be arbitrarily large.
• This shows a quadratic separation between matroid center and $k$-center, for which the Doubling algorithm gives an $8$-approximation using $O(k)$-space and one pass.