Home / Curated / Algorithms / Amortized-Filtering and Iterative-Filtering for Optimal Logarithmic-Adaptivity Submodular Maximization

Amortized-Filtering and Iterative-Filtering for Optimal Logarithmic-Adaptivity Submodular Maximization

Algorithms AIMech:AmortizedFilteringForLogarithmicAdaptivitySubmodularMaximization DRAFT

Aliases: Balkanski-Rubinstein-Singer Amortized-Filtering Algorithm, Iterative-Filtering and Amortized-Filtering for Low-Adaptivity Submodular Maximization, Logarithmic-Adaptivity (1 - 1/e - epsilon) Submodular Maximization

Amortized-Filtering and Iterative-Filtering for Optimal Logarithmic-Adaptivity Submodular Maximization is a parallel value-oracle algorithmic paradigm introduced by Balkanski, Rubinstein, and Singer (2018, 2019) for maximizing a monotone submodular function f : 2^N -> R_+ subject to a cardinality constraint |S| <= k in O(log n) adaptive rounds. Rather than adding single elements sequentially over k rounds, the algorithm adds blocks R ~ U(X, k/r) of size k/r in r = 20*epsilon^{-1}log_{1+epsilon/2}(n) iterations by filtering out elements a in X whose expected marginal contribution E_{R~U(X)}[f_{S union (R\{a})}(a)] falls below (1+epsilon/2)(1-epsilon)(OPT - f(S))/k while E_{R~U(X)}[f_S(R)] < (1-epsilon)(OPT - f(S))/r, and amortizes the filtering rounds across 20/epsilon epochs (each bounded by f_S(T) < (epsilon/20)(OPT - f(S))) so that at most log_{1+epsilon/2}(n) filtering steps occur per epoch, achieving the optimal (1 - 1/e - epsilon) approximation in O(epsilon^{-1}log_{1+epsilon/3} n) adaptive rounds.

Identity Notes & Concept Scope Distinct from AIMech:GreeDiTwoStageDistributedSubmodularMaximization (Round 359), which partitions data across MapReduce machines but runs sequential k-round greedy selection on each machine (Omega(k) adaptivity), and from AIMech:StochasticGreedyLinearTimeMonotoneSubmodularMaximization (Round 348), which reduces total oracle evaluations to O(n log(1/epsilon)) across k sequential rounds. Also distinct from AIMech:SieveStreamingAndSieveStreamingPlusPlusForSubmodularMaximization (Round 350), which is a single-pass streaming threshold algorithm achieving 1/2 - epsilon rather than a low-adaptivity parallel algorithm achieving 1 - 1/e - epsilon.

Claims & Grounded Evidence

3 Claims

Mechanism #r360-claim-iterative-filtering-geometric-shrinkage-and-survival-value

In each non-terminating round i of Filter(N, S, r) (Algorithm 2) where E_{R~U(X_i, k/r)}[f_S(R)] < (1 - epsilon)(OPT - f(S))/r, discarding all elements a with E_{R~U(X_i)}[f_{S union (R\{a})}(a)] < (1 + epsilon/2)(1 - epsilon)(OPT - f(S))/k reduces the surviving candidate pool geometrically as |X_{i+1}| < |X_i| / (1 + epsilon/2) (Lemma 3) while preserving a subset T of the optimal solution O among the surviving elements X_rho with marginal value f_S(X_rho) >= (1/r)*(1 - epsilon)*(OPT - f(S)) whenever r >= 20*rho*epsilon^{-1} (Lemmas 1-2), guaranteeing termination of Filter in at most log_{1+epsilon/2}(n) rounds (Lemma 4) and a (1 - 1/e - epsilon) approximation for Iterative-Filtering (Algorithm 1) in O(log^2 n) adaptive rounds (Theorem 1).

supports Source: An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation · Locator: Section 2.1-2.3, Algorithms 1-2, Lemmas 1, 2, 3, and 4, and Theorem 1, pp. 4-8; Appendix C, pp. 18-20

Mechanism #r360-claim-amortized-filtering-across-epochs-in-logarithmic-rounds

Amortized-Filtering (Algorithm 3) partitions execution into at most 20/epsilon epochs during which the surviving pool X is reused across block additions T <- T union R until f_S(T) >= (epsilon/20)(OPT - f(S)) or |S union T| = k; because the solution value increases by at most (epsilon/20)(OPT - f(S_j)) within epoch j, surviving elements after rho filtering rounds satisfy f_{S_j^+}(X_rho) >= (epsilon/4)(1 - epsilon)(OPT - f(S_j)) (Lemmas 5-6), bounding the total number of filtering rounds per epoch by at most log_{1+epsilon/2}(n) (Lemma 7) and achieving a (1 - 1/e - epsilon) approximation in at most 20*epsilon^{-1}*log_{1+epsilon/2}(n) + (epsilon/20)^{-1}*log_{1+epsilon/2}(n) = O(epsilon^{-1} log n) adaptive rounds (Theorem 2).

supports Source: An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation · Locator: Section 3.1-3.3, Algorithm 3, Lemmas 5, 6, and 7, and Theorem 2, pp. 8-10; Appendix D, pp. 20-22

Mechanism #r360-claim-monte-carlo-marginal-estimation-and-parallel-opt-guessing

In the full randomized algorithm Amortized-Filtering-Full (Algorithms 4-7), running log_{(1-epsilon/20)^{-1}}(n) parallel branches over geometric OPT guesses v_i = (1 + epsilon)^i * max_{a in N} f(a) and estimating E[f_S(R)] and E[f_{S union (R\{a})}(a)] in a single non-adaptive round via Hoeffding concentration with m = O(n*((k + log_{1+epsilon/3} n)/epsilon)^2 * log(n/delta)) uniform samples preserves geometric candidate shrinkage |X_{i+1}| < |X_i|/(1 + epsilon/3) (Lemma 10) and obtains a (1 - 1/e - epsilon) approximation with probability at least 1 - delta in O(epsilon^{-1} log_{1+epsilon/3} n) adaptive steps and O(n*log_{(1-epsilon/20)^{-1}}(n)*((k + log_{1+epsilon/3} n)/epsilon)^2 * log(n/delta)) oracle queries per round (Lemmas 8-14 and Theorem 3).

supports Source: An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation · Locator: Section 3.3, Theorem 3, p. 10; Appendix E, Algorithms 4-7, Lemmas 8-14, and Proof of Theorem 3, pp. 23-30

⚠️ Curated Limitations & Negative Results

Achieving the theoretical (1 - 1/e - epsilon) guarantee without knowing OPT or exact expectations requires O(n * log_{(1-epsilon/20)^{-1}}(n) * ((k + log n)/epsilon)^2 * log(n/delta)) parallel oracle queries per adaptive round (Theorem 3, p. 10) and does not directly bound per-machine memory in the MapReduce model (Appendix A.2.2, p. 17).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:Clustering` Clustering	related_match	Enables logarithmic-round parallel submodular data summarization and clustering.
`AIO:DimensionalityReduction` Dimensionality Reduction	related_match	Selects cardinality-constrained representative subsets in O(log n) adaptive parallel rounds.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r360-primary-pdf`	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation Eric Balkanski, Aviad Rubinstein, Yaron Singer	primary paper full_text	ID: https://api.crossref.org/works/10.1145/3188745.3188752 sha256:a2f10b778f54…
`r360-arxiv-abs`	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation (arXiv abstract) Eric Balkanski, Aviad Rubinstein, Yaron Singer	primary paper abstract_only	ID: https://arxiv.org/abs/1804.06355 sha256:0fa2de0095ae…
`r360-metadata-cr`	An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation (Crossref metadata) Eric Balkanski, Aviad Rubinstein, Yaron Singer	primary paper abstract_only	ID: https://api.crossref.org/works/10.1145/3188745.3188752 sha256:120c44f8b29a…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T07:23:00Z

Updated: 2026-10-19T07:23:00Z

Source File: data/curated/AmortizedFilteringForLogarithmicAdaptivitySubmodularMaximization.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories