2026-07-22T13:00:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16400 2024-03-06T10:57:23Z ddc:004 open_access

Streaming Submodular Maximization Under Matroid Constraints Feldman, Moran Liu, Paul Norouzi-Fard, Ashkan Svensson, Ola Zenklusen, Rico Submodular maximization streaming matroid random order Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are: - A single-pass streaming algorithm that uses Õ(k) memory and achieves an approximation guarantee of 0.3178. - A multi-pass streaming algorithm that uses Õ(k) memory and achieves an approximation guarantee of (1-1/e - ε) by taking a constant (depending on ε) number of passes over the stream. This improves on the previously best approximation guarantees of 1/4 and 1/2 for single-pass and multi-pass streaming algorithms, respectively. In fact, our multi-pass streaming algorithm is tight in that any algorithm with a better guarantee than 1/2 must make several passes through the stream and any algorithm that beats our guarantee of 1-1/e must make linearly many passes (as well as an exponential number of value oracle queries). Moreover, we show how the approach we use for multi-pass streaming can be further strengthened if the elements of the stream arrive in uniformly random order, implying an improved result for p-matchoid constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moran Feldman and Paul Liu and Ashkan Norouzi-Fard and Ola Svensson and Rico Zenklusen 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.59 urn:nbn:de:0030-drops-164007 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.59 eng https://creativecommons.org/licenses/by/4.0/legalcode