Chien-Chung Huang, Robust Sparsification for Matroid Intersection with Applications

The matroid intersection problem is a fundamental problem in combinatorial optimization. In this problem we are given two matroids and the goal is to find the largest common independent set in both matroids. This problem was introduced and solved by Edmonds in the 70s. The importance of matroid intersection stems from the large variety of combinatorial optimization problems it captures; well-known examples in computer science include bipartite matching and packing of spanning trees/arborescences.

In this talk, we introduce a “sparsifer” for the matroid intersection problem and use it to design algorithms for two problems closely related to streaming: a one-way communication protocol and a streaming algorithm in the random-order streaming model.

This is a joint-work with François Sellier.