Source-linked AI summary
Streaming Algorithms for Submodular Function Maximization
Chandra Chekuri, Shalmoli Gupta, Kent Quanrud
TL;DR
Streaming maximization of submodular functions has largely focused on monotone objectives, despite the importance of space-efficient processing for large datasets. This paper gives deterministic and randomized one-pass algorithms for non-monotone objectives under p-matchoid constraints, obtaining an Ω(1/p)-approximation with O(k log k) space.
Problem
Prior streaming work on submodular maximization focused on monotone functions, although that assumption is described as restrictive and large datasets motivate space-efficient streaming algorithms.
Source: §1 · p. 2Method
The paper adapts randomized buffering and deterministic two-instance streaming techniques to non-monotone maximization under p-matchoid constraints.
Source: §1 · pp. 2, 5Results
Deterministic and randomized one-pass algorithms achieve an Ω(1/p)-approximation using O(k log k) space for nonnegative submodular maximization under p-matchoid constraints.
Source: §1 · p. 3Takeaways & Limitations
The algorithms extend streaming non-monotone submodular maximization beyond cardinality constraints to p-matchoids, which generalize several basic combinatorial constraints.
Source: §1 · pp. 2–3The model requires value and membership oracles and an explicit upper bound k, and may not directly fit some important scenarios.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We consider the problem of maximizing a nonnegative submodular set function $f:2^{\mathcal{N}} \rightarrow \mathbb{R}^+$ subject to a $p$-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are {\em non-monotone}. We describe deterministic and randomized algorithms that obtain a $\Omega(\frac{1}{p})$-approximation using $O(k \log k)$-space, where $k$ is an upper bound on the cardinality of the desired set. The model assumes value oracle access to $f$ and membership oracles for the matroids defining the $p$-matchoid constraint.
1. Introduction
The paper studies space-efficient streaming maximization of nonnegative submodular functions under combinatorial constraints, including non-monotone functions. It presents deterministic and randomized one-pass algorithms with an Ω(1/p)-approximation and O(k log k) space for p-matchoid constraints.
1. Introduction
- Large datasets motivate space-efficient streaming methods, while prior streaming work focused on monotone submodular functions, an assumption described as restrictive in theory and practice.Constrained submodular maximization is NP-hard even under a cardinality constraint and has applications including data summarization and influence maximization.Source: §1 · p. 2
- p-matchoids generalize cardinality constraints, intersections of p matroids, and matchings in graphs and hypergraphs.The paper also explicitly treats cardinality constraints and obtains an improved bound for that case.Source: §1 · p. 2
- The model assumes value-oracle access to the objective, membership-oracle access to the independence family, and an explicit upper bound k on solution size.The paper notes that this model may not directly apply to some important scenarios.Source: §1 · p. 3
- Ω(1/p) approximation and O(k log k) space are achieved by deterministic and randomized one-pass algorithms for nonnegative submodular maximization under p-matchoid constraints.The randomized algorithm has better constants; the paper describes these as the first streaming algorithms for non-monotone submodular maximization under constraints beyond cardinality.Source: §1 · p. 3
- The randomized algorithm buffers high-value arriving elements for later selection, while the deterministic algorithm sends rejected elements to a second streaming instance and post-processes elements selected by the first.Both approaches limit how many elements are added to the running solution, using additive thresholds to bound the post-processor's input.Source: §1 · pp. 4–5
- Earlier streaming algorithms addressed modular or monotone submodular objectives; the paper distinguishes streaming from preemptive online models, where elements already selected may later be discarded.The cited prior streaming work includes cardinality algorithms and algorithms for intersections of p matroids and rank-p hypergraphs.Source: §1 · pp. 5–6
2. Preliminaries
The preliminaries define matroid-based p-matchoid constraints and introduce incremental values, which decompose a set's value and inherit diminishing returns from submodularity.
Matchoids
- A p-matchoid combines matroids on overlapping ground sets, with each element belonging to at most p matroids; this includes matchings and matroid intersections.Feasible sets must be independent in every matroid.Source: §2 · p. 7
Offline optimization
- For nonnegative submodular maximization under a p-matchoid, offline algorithms provide an Ω(1/p)-approximation, with stronger bounds possible for simpler constraints.The paper uses such an algorithm as a black box called Offline, with ratio γ_p.Source: §2 · p. 7
Incremental Value
- Incremental value assigns each element the marginal value against the earlier elements of a set in a fixed ordering, so the incremental values sum to the set's value.This additive decomposition avoids the inequality-only relationship obtained by summing ordinary marginals.Source: §2 · p. 7
- For submodular functions, an element's incremental value cannot increase when its containing set grows, and conditioning on an additional set gives the stated submodularity inequality.These properties follow from comparing the earlier elements in the fixed ordering.Source: §2 · pp. 7–8
3. Streaming Greedy
Streaming-Greedy maintains a feasible set by deciding whether to discard each arriving element or add it through an exchange, and its monotone guarantee makes it a building block for later algorithms. Its analysis bounds the elements ever selected and uses p-matchoid exchanges to relate them to a feasible comparison set.
3. Streaming Greedy
- Streaming-Greedy gives an Ω(1/p)-approximation for monotone submodular functions, but performs poorly for non-monotone functions.The algorithm is presented as a building block for randomized and deterministic algorithms for the non-monotone case.Source: §3 · p. 8
- Each arriving element is discarded or added by exchanging a chosen subset of the current feasible set, with the exchange threshold tuned by α and β.The algorithm uses an additive threshold and incremental values, which rise as other elements are removed; these changes are described as crucial for later non-monotone algorithms.Source: §3 · p. 8
3.1. Relating f(U) to f( ˜S)
- |U| ≤ OPT/α under threshold α, bounding the number of ever-selected elements even when marginal values can be negative.Choosing α = cOPT/k gives |U| ≤ k/c, a bound used in later analyses of the non-monotone algorithms.Source: §3 · p. 9
3.2. Upper bounding f(U ∪T)
- A p-matchoid exchange mapping charges each final-set element at most p times and each deleted element at most p − 1 times across a feasible comparison set.The analysis uses this mapping to upper bound f(U ∪ T).Source: §3.2 · p. 12
3.3. A bound for the monotone case
- For monotone submodular functions, Streaming-Greedy(0,1) is online and returns a feasible set, with bounds matching.The incremental-value updates require more value-oracle calls, while the number of reevaluations is tied to deletions and bounded by the matchoid rank.Source: §3.3 · p. 15
4. Randomized Streaming Greedy
Randomized-Streaming-Greedy adapts Streaming-Greedy with a randomized buffer and an offline solution for buffered elements. For cardinality constraints, its specialized version guarantees a value of at least (1−ϵ)/(2+e)·OPT.
4. Randomized Streaming Greedy
- A randomized buffer limits selection probability: when it reaches K elements, one is chosen uniformly and added to the running solution.The algorithm processes the remaining buffer offline and returns the better of that solution and the running solution.Source: §4 · p. 15
4.4. Overall Analysis
- For fixed α and β, the overall analysis combines earlier lemmas to bound f(T) against the returned solution.The preceding analysis identifies β=1 as optimal and chooses α in proportion to OPT/k.Source: §4 · p. 16, §4.4 · p. 19
4.1. Reducing to Streaming-Greedy
- Setting K=1 reduces Randomized-Streaming-Greedy to Streaming-Greedy; the buffer otherwise filters and reorders the stream.For any fixed buffer random bits, the Streaming-Greedy analysis still applies to the reordered stream.Source: §4.1 · p. 17
4.2. Upper bounding f(U ∪T) by f( ˆS)
- The analysis splits the comparator set into elements outside the final buffer and those inside it, bounding the two portions using Streaming-Greedy and Offline.The resulting bounds relate f(U ∪ T) to the value of the returned solution.Source: §4.2 · p. 18
4.3. Upper bounding f(T) by f(U ∪T)
- The buffer bounds each element’s probability of entering U, enabling a lower bound on E[f(U ∪ T)] as a fraction of f(T).The argument uses the bound E[f(R ∪ Y)] ≥ (1−ρ)f(Y) when each element is selected into R with probability at most ρ.Source: §4.3 · p. 19
4.5. A bound for approximate α
- For fixed ϵ > 0, Lemma 21 gives a statement under the condition ϵ·OPT/4k ≤ α ≤ ϵ·OPT/2k, but the cited passage does not show its conclusion.The algorithm does not know OPT and will try to estimate it approximately; the passage describes the bound when α is within a factor of 2 of ϵOPT/2k.Source: §4.5 · p. 20
4.6. Efficiently estimating α
- The algorithm guesses α using parallel instances; updating the guesses as the stream arrives reduces the approach to one pass.The guesses are maintained as the best singleton changes, and an appropriate guess attains the bound from Lemma 20.Source: §4.6 · pp. 20–21
4.7. Simpler algorithm and better bound for cardinality constraint
- For cardinality constraints, the algorithm returns a set of size at most k with value at least (1−ϵ)/(2+e)·OPT.Here OPT is the maximum value attainable by a set of at most k elements.Source: §4.7 · p. 23
5. A Deterministic Algorithm via Iterated Greedy
Iterated-Streaming-Greedy combines streaming solutions with an offline solution on elements retained from the first pass. Pipelining the two streaming instances yields a one-pass algorithm, and a deterministic offline routine makes the algorithm deterministic.
5. A Deterministic Algorithm via Iterated Greedy
- The deterministic algorithm adapts Gupta et al.’s framework by using Streaming-Greedy as the black box for the monotone case.The method runs the streaming algorithm over the original ground set, then processes elements rejected outright in a downstream instance.Source: §5 · p. 23
- Iterated-Streaming-Greedy forms three candidates: a first-pass streaming solution, a second streaming solution on rejected elements, and an offline solution on the first-pass retained set.It returns the candidate with the highest value; pipelining the streaming instances makes this a one-pass algorithm.Source: §5 · pp. 23–24
- If the offline algorithm is deterministic, Iterated-Streaming-Greedy is deterministic and its bound holds without expectation.The theorem assumes an offline algorithm with approximation ratio γp for the p-matchoid problem.Source: §5 · p. 25
A. Exchange lemmas for matroids
The exchange lemmas establish how matroid span relations support a matching from independent elements to reachable sinks in a directed acyclic graph.
A. Exchange lemmas for matroids
- If S spans x and T+x spans y in a matroid, then S∪T spans y.The proof extends S to a base in S∪T and uses that base’s spanning property.Source: A. Exchange lemmas for matroids · p. 28
- In a directed acyclic graph where each non-sink’s outgoing neighbors span it, an independent set with no paths between its members injects into reachable sinks.Each element maps to a sink reachable from it.Source: A. Exchange lemmas for matroids · p. 28
- For the bipartite base case, Hall’s theorem gives the injection because the outgoing neighbors of each subset span that subset.The proof reduces the general case by removing internal vertices while preserving sinks and reachability.Source: A. Exchange lemmas for matroids · p. 29