Lemma 3.10:
ProvedGeomRescale.lemma_3_10combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Throughout Algorithm Rescaling-SFM, holds, for the current and .
The ellipsoid therefore confines the feasible region, while its volume shrinks by Lemma 3.12.
Differences from the source:
- encoding: throughout the algorithm / at every stage → every state reachable from the initial state, for as in the goal; reason: a run is a relation, so this covers all tie-breaks and argmins; the placeholder of the state before lines 2–3 is included, and the statement holds there too
- encoding: a ground set with elements →
1 ≤ n; reason: the parameter of Algorithm 2 is undefined at ; the hypothesis excludes only that case - generalization: the run of Algorithm 2 with → the runs for every , with ; reason: gives the paper's run, with rounded as in Theorem 3.6; the statement holds on every such run
- reading: with no case for → at in the step relation; reason: occurs (for at line 2 of Algorithm 1), and the run needs a value there
- reading: in (10) and in line 8 of Algorithm 2, returned after line 15 of Algorithm 1 incremented → , the bases the call computed; reason: line 15 has incremented , so no was computed
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_GeomRescale_fR import Definitions.Def_GeomRescale_Ltwo import Definitions.Def_GeomRescale_Reachable import Definitions.Def_GeomRescale_ellipsoid import Definitions.Def_GeomRescale_Fmu open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Lemma 3.10 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.10, p.11, proved with Lemma A.1, p.31): throughout Algorithm
Rescaling-SFM, `F_μ ⊆ E(R)` holds.
**Formalization Note.** "Throughout" is every reachable state, with the current `μ` and `R`. -/
theorem lemma_3_10 {n : ℕ} (hn : 1 ≤ n) (f : Finset (Fin n) → ℤ) (hsub : Submodular (fR f))
(hf0 : f ∅ = 0) (Λ : ℝ) (hΛ : Ltwo (fR f) ≤ Λ) (s : St n) (hs : Reachable f Λ s) :
Fmu (fR f) (s.vn.μ : ℝ) ⊆ ellipsoid s.R := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.10, p.11, and Lemma A.1, p.31
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.