Claim 2.2: the complexity parameters are equivalent
ProvedGeomRescale.claim_2_2combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Let be submodular with . The maxima defining and are attained, and:
- ;
- , in the form ;
- for every , for all ; hence and ;
- for all .
The running time depends on these parameters only up to a constant inside the logarithm.
Differences from the source:
- encoding: , defined as maxima →
sSup, with a conjunct stating that they are attained; reason: a realsSupof an unbounded set is - generalization: → ; reason: explicit constants imply the
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_SchrijverSFM_Alg_Setting import Definitions.Def_GeomRescale_norm1 import Definitions.Def_GeomRescale_norm2 import Definitions.Def_GeomRescale_Lone import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_Ff import Definitions.Def_GeomRescale_alpha open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Claim 2.2 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Claim 2.2, p.4), with the maxima defining `L_f`, `L_{f,2}` attained.
(i) `L_{f,2} ≤ L_f ≤ √n L_{f,2}`. (ii) `L_f = Θ(F_f)`, as `F_f ≤ L_f ≤ 3F_f`.
(iii) `|z(v)| ≤ α(v)` for `z ∈ B(f)`; hence `L_f ≤ ‖α‖₁ = α(V)` and `L_{f,2} ≤ ‖α‖₂`.
(iv) `α(v) ≤ 2F_f`.
**Formalization Note.** `Lone`, `Ltwo` are `sSup`s, so the first conjunct records that they are the
maxima of the page. The `Θ` of (ii) is written with its constants `1` and `3`. -/
theorem claim_2_2 {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f) (hf0 : f ∅ = 0) :
(IsGreatest (norm1 '' baseB f) (Lone f) ∧ IsGreatest (norm2 '' baseB f) (Ltwo f)) ∧
(Ltwo f ≤ Lone f ∧ Lone f ≤ √(n : ℝ) * Ltwo f) ∧
(Ff f ≤ Lone f ∧ Lone f ≤ 3 * Ff f) ∧
((∀ z ∈ baseB f, ∀ v, |z v| ≤ alpha f v) ∧
Lone f ≤ norm1 (alpha f) ∧ norm1 (alpha f) = ∑ v, alpha f v ∧
Ltwo f ≤ norm2 (alpha f)) ∧
∀ v, alpha f v ≤ 2 * Ff f := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Claim 2.2, p.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.