Display (9), §3, p. 349 — diminishing marginal values: f(Y ∪ {v}) − f(Y) ≤ f(X ∪ {v}) − f(X)
ProvedSchrijverSFM.Alg.marginal_antitonediminishing-returnsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-function
Let and let be a submodular real function on the subsets of , i.e. for all . If and , then
The marginal value of adding an element can only decrease as the set grows. In the paper this inequality is the tool behind the comparison (8) of the greedy vectors of an order and of a moved order.
Formalization Note The normalization of the paper is not needed here and is not assumed.
Preamble
import Mathlib import Definitions.Def_SchrijverSFM_Alg_Setting
Formal statement
namespace SchrijverSFM.Alg
open NonmonotoneSubmod.Shared
theorem marginal_antitone {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f) :
∀ X Y : Finset (Fin n), X ⊆ Y → ∀ v : Fin n, v ∉ Y →
f (insert v Y) - f Y ≤ f (insert v X) - f X := by sorry
end SchrijverSFM.Alg
Source
Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B 80 (2000), p. 349, display (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.