Theorem 1.5 — a -approximation for monotone submodular maximization under a matroid constraint in rounds
OpenParallelMatroidBasis.Main.Supplement.theorem_1_5There is an exponent such that for every there are constants and such that for every there is one randomized parallel algorithm — one procedure for every ground-set size , seeing a matroid on only through independence queries and a set function only through value queries — such that for all , every such matroid and every monotone submodular (; ):
- every run uses at most adaptive rounds;
- every run makes at most independence queries to and at most queries to in total;
- if , with probability at least the output satisfies
The constants , and the exponent do not depend on . This improves the rounds of [KPS26] for the independence-query model; no normalization is assumed.
Formalization Note The query model is MultiOracle's SubmodAlgorithm. Monotonicity and submodularity reuse the published SubsamplingSM.Offline.IsMonotoneSetFn and NonmonotoneSubmod.Shared.Submodular; nonnegativity is a separate hypothesis. The maximum is encoded as " for every independent ". is read as a fixed power of , "with high probability" as failure at most for every .
Differences from the source:
- encoding: an algorithm making rounds of polynomially many queries → one ExactParallelSampling.QuasiUniform.Protocol (Finset (Fin n) ⊕ Finset (Fin n)) (Bool ⊕ ℝ) (Finset (Fin n)) for every n, with a uniform [0,1]^ℕ tape and measurable next-action maps; reason: the batches and the output depend only on the tape and on earlier answers; a tape of uniform reals simulates any finite random choice, and measurability only restricts the algorithm to be exhibited
- encoding: a matroid M on n elements → a Matroid (Fin n) with ground set univ; reason: the algorithm knows the n labels of the ground set, as in the source's oracle model (same convention as the base mission)
- encoding: a monotone submodular function f : 2^E → R≥0, accessed by queries → f : Finset (Fin n) → ℝ with IsMonotoneSetFn f, Submodular f (lattice inequality) and 0 ≤ f S for all S; value queries return f(T) exactly; reason: the source's three conditions, with no normalization f(∅) = 0, as in the source
- reading: for any ε > 0, an Õ(n^{1/3}/ε^3) round algorithm → ∃ k : ℕ, then for each c ∃ C > 0 and d, then for each ε > 0 an algorithm with at most C(1 + n^{1/3}(log₂(n+2))^k/ε³) rounds on every run; reason: Õ hides a polylogarithmic factor in n; C, d, k uniform in ε is the stronger reading (the O(·) keeps 1/ε³ explicit); log₂(n+2) ≥ 1 keeps the factor defined at n ≤ 1
- reading: polynomially many independence queries to M and polynomially many queries to f → at most (n+1)^d independence queries and at most (n+1)^d value queries over the whole run, d independent of ε; reason: the source states query totals, not per-round counts; a total bound is the stronger reading and implies a per-round bound
- reading: with high probability → for every c > 0 (with constants and algorithm depending on c), for n ≥ 1 the success probability is at least 1 − n^{−c}; reason: the base mission's reading of the paper's 'with high probability'; the proofs amplify to inverse-polynomial failure for an arbitrary exponent (PDF pp.37, 41); this is the stronger reading
- encoding: S ∈ I with f(S) ≥ (1/2 − ε) max_{T∈I} f(T) → M.Indep S and (1/2 − ε) f(T) ≤ f(S) for every independent T; reason: the maximum over the finite nonempty family I is attained, so the two conditions coincide
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SubsamplingSM_Offline_IsMonotoneSetFn import Definitions.Def_ParallelMatroidBasis_Main_Supplement_MultiOracle noncomputable section open Classical MeasureTheory
namespace ParallelMatroidBasis.Main.Supplement
/-- Theorem 1.5, PDF p.5 (printed p.3), with `Õ(·)` read as a polylogarithmic factor
`(log₂ (n+2))^k` and "with high probability" as failure probability at most `n^{−c}` for every
fixed `c > 0`. There is `k` such that for every `c > 0` there are `C > 0` and `d` such that for
every `ε > 0` there is one parallel algorithm `A` (a protocol for every `n`, seeing `M` only
through independence queries and `f` only through value queries) such that for all `n`, every
matroid `M` on `Fin n` and every monotone submodular `f : 2^{Fin n} → ℝ≥0`: every run uses at most
`C (1 + n^{1/3} (log₂ (n+2))^k / ε³)` rounds, at most `(n+1)^d` independence queries and at most
`(n+1)^d` value queries in total, and for `n ≥ 1`, with probability at least `1 − n^{−c}`, the
output `S` is independent and `f(S) ≥ (1/2 − ε) max_{T ∈ I} f(T)`. -/
theorem theorem_1_5 :
∃ k : ℕ, ∀ c : ℝ, 0 < c →
∃ (C : ℝ) (d : ℕ), 0 < C ∧ ∀ ε : ℝ, 0 < ε →
∃ A : SubmodAlgorithm,
∀ (n : ℕ) (M : Matroid (Fin n)) (f : Finset (Fin n) → ℝ), M.E = Set.univ →
SubsamplingSM.Offline.IsMonotoneSetFn f → NonmonotoneSubmod.Shared.Submodular f →
(∀ S, 0 ≤ f S) →
RunRoundsAtMost (A n) (submodOracle M f)
(C * (1 + (n : ℝ) ^ ((1 : ℝ) / 3) * (Real.logb 2 ((n : ℝ) + 2)) ^ k / ε ^ 3)) ∧
RunTotalQueriesAtMost (A n) (submodOracle M f) IsIndepQuery ((n + 1) ^ d) ∧
RunTotalQueriesAtMost (A n) (submodOracle M f) IsValueQuery ((n + 1) ^ d) ∧
(1 ≤ n → ENNReal.ofReal (1 - (n : ℝ) ^ (-c)) ≤ submodSuccessProb A n M f ε)
:= by sorry
end ParallelMatroidBasis.Main.Supplement