§4–§5, pp. 351–352 — Schrijver's algorithm: Case 1 returns a minimizer (16), every Case 2 state has a successor, and every run has at most |V|⁶ iterations
ProvedSchrijverSFM.Alg.schrijver_algorithmLet and let be a submodular real function on the subsets of with . Consider Schrijver's algorithm, whose states are convex combinations of greedy vectors, with digraph , and . Then:
- (Correctness, (16).) For every valid state in Case 1 (no directed path from to ), the set of vertices that can reach minimizes : for all .
- (Well-definedness.) For every valid state in Case 2, one iteration of the algorithm can be carried out.
- (Running time, §5.) Every run of iterations from an initial state satisfies
Together: from any initial order, the algorithm reaches Case 1 after at most iterations, and then returns a minimizer of . This is the main result of the paper; it gives a combinatorial algorithm for submodular function minimization whose number of iterations is bounded by a polynomial in alone.
Formalization Note The ground set is Fin n and ; "largest" in the choice of and refers to the order of Fin n; values are real rather than in an arbitrary ordered field. An iteration is the relation Step of the setting file, which admits every choice the paper leaves open. Conjunct 2 rules out a vacuous reading of conjunct 3. "Strongly polynomial time" and the number of oracle calls are not formalized (there is no machine model); only the iteration count is.
import Mathlib import Definitions.Def_SchrijverSFM_Alg_Setting
namespace SchrijverSFM.Alg
open NonmonotoneSubmod.Shared
theorem schrijver_algorithm {n : ℕ} (f : Finset (Fin n) → ℝ) (hsub : Submodular f)
(hf0 : f ∅ = 0) :
(∀ S : State n, Valid S → caseOne f S → ∀ W : Finset (Fin n), f (caseOneSet f S) ≤ f W) ∧
(∀ S : State n, Valid S → ¬ caseOne f S → ∃ S' : State n, Step f S S') ∧
(∀ (S : ℕ → State n) (m : ℕ), IsRun f S m → m ≤ n ^ 6) := by sorry
end SchrijverSFM.Alg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.