Lemma 3.4:
ProvedGeomRescale.lemma_3_4combinatorial-optimizationp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rescalingsubmodular-function-minimizationvon-neumann-algorithm
Let be submodular with , let with for some . Then
So the enlargement does not change the complexity parameter by more than a constant factor.
Differences from the source:
- generalization: integer valued (standing assumption of Section 3) → and real; reason: the proof uses no integrality; apply it to
fR fand an integer for the page's statement
Preamble
import Mathlib import Definitions.Def_NonmonotoneSubmod_Shared_Submodular import Definitions.Def_GeomRescale_enlarge import Definitions.Def_GeomRescale_Lone open NonmonotoneSubmod.Shared open SchrijverSFM.Alg
Formal statement
namespace GeomRescale
/-- Lemma 3.4 (Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.4, p.7): if `μ ≥ max {0, −f(V)}` and `μ = −f(W)` for some `W ⊆ V`,
then `L_{f_μ} ≤ 4L_f`. -/
theorem lemma_3_4 {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f) (hf0 : f ∅ = 0)
(μ : ℝ) (hμ : max 0 (-f Finset.univ) ≤ μ) (W : Finset (Fin n)) (hW : μ = -f W) :
Lone (enlarge f μ) ≤ 4 * Lone f := by sorry
end GeomRescale
Source
Dadush, Végh & Zambelli, Geometric Rescaling Algorithms for Submodular Function Minimization, arXiv:1707.05065v4, Lemma 3.4, p.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.