Semi-streaming algorithms for submodular matroid intersection (Q5918428)

The authors present a semi-streaming \(2+\epsilon\)-approximation algorithm for the weighted matroid intersection problem. This improves the previously known best approximation guarantee of \(4+\epsilon\) given in [\textit{M. Crouch} and \textit{D. M. Stubbs}, LIPIcs -- Leibniz Int. Proc. Inform. 28, 96--104 (2014; Zbl 1359.68306)] (the intersection of two matroids is a special case of a \(2\)-system). The motivation for looking at approximation algorithms in the semi-streaming model is to consider cases in which the input data does not fit into memory. In the semi-streaming model the input data is revealed one-by-one in a stream, and at each time step the algorithm has access to the currently revealed item and its (bounded) memory. For example, the maximum matching in the semi-streaming model for graphs \(G\) reveals the edges \(e_1, e_2, \ldots, e_{|E(G)|}\) one after another and the algorithm is only allowed to store \(\mathcal O(|V(G)|\mathrm{polylog}(|V(G)|))\) bits in its memory. In this setting, the greedy algorithm is the semi-streaming algorithm with the best known approximation guarantee, namely it is an \(2\)-approximation. The weighted case is more difficult and only recently a \(2+\epsilon\)-approximation algorithm using the local ratio method was found, see [\textit{A. Paz} and \textit{G. Schwartzman}, ACM Trans. Algorithms 15, No. 2, Article No. 18, 15 p. (2019; Zbl 1454.68187)]. This algorithm first selects a small set \(S\) of the edges in the input stream, and then calculates a perfect matching using the greedy algorithm on \(S\), where the edges of \(S\) are considered in reverse order. The bipartite matching problem can be formulated as an intersection of two matroids. Thus, it is natural to investigate whether the algorithm of Paz and Schwartzman also gives an \(2+\epsilon\)-approximation algorithm for the intersection of two matroids. Garg, Jordan, and Svensson give an example showing that this is not the case. They adapt the algorithm of Paz and Schwartzman to the weighted matroid intersection of two matroids using so-called kernels in oriented matroids. This adaption together with a trick to reduce the memory consumption yields an \(2+\epsilon\)-approximation algorihm in the semi-streaming model for each fixed \(\epsilon > 0\). The article concludes with a remark that the analysis used cannot be generalized to the intersection of more than two matroids. The authors conjecture that their methods nevertheless give a \(k+\epsilon\)-approximation algorithm in the semi-streaming model for the weighted intersection of \(k\) matroids. An extended version of the article can be found at \url{https://arxiv.org/abs/2102.04348}. For the entire collection see [Zbl 1476.90004].