Google Research

Submodular Maximization Subject to Matroid Intersection on the Fly

  • Ashkan Norouzi Fard
  • Moran Feldman
  • Ola Svensson
  • Rico Zenklusen
30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany, Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik, 52:1-52:14

Abstract

Despite a surge of interest in submodular maximization in the streaming and online models, there remain significant gaps in our knowledge about what can be achieved in these settings, especially when dealing with multiple constraints. In this work, we nearly close various gaps in submodular maximization subject to k matroid constraints in both the streaming and online settings. We present a new hardness result implying that exponential memory in k is needed to obtain an o(k/log k)-approximation in the streaming setting. (The same hardness construction also rules out o(k/log k)-competitive (preemptive) online algorithms.) This implies near optimality of prior algorithms. For the same setting, we show that one can nevertheless obtain a constant-factor approximation using memory that is only logarithmic in the size of the ground set. Finally, for bipartite matching constraints, a well-known special case of matroid intersection, we present a new technique to obtain hardness bounds that are significantly stronger than those obtained with prior approaches. Prior results left it open whether a 2-approximation may exist in this setting, whereas, under some complexity theoretic assumption, we can rule out approximation factors below 3.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work