Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 14 — Algorithm 5 returns a path with its exact factor and runtime

Open
SubmodMDP.Policies.Supplement.lemma_14

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-algorithmsorienteeringp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1submodular-optimization

Let G=(V,A)G=(V,A)G=(V,A) be a well-formed layered graph with layers V1,…,VHV_1,\ldots,V_HV1​,…,VH​, where H=drH=d^rH=dr, d≥2d\ge2d≥2 and r≥0r\ge0r≥0 are integers. Let S⊆V1S\subseteq V_1S⊆V1​ and T⊆VHT\subseteq V_HT⊆VH​, assume an SSS-TTT path exists, and let fff be a nonnegative monotone submodular value oracle.

There are one positive absolute integer ccc and one deterministic program, uniform over all these data and oracles, implementing Algorithm 5 in at most (∣V∣+1)c(r+1)(|V|+1)^{c(r+1)}(∣V∣+1)c(r+1) charged operations. Its result is a path P≠⊥P\ne\botP=⊥ from SSS to TTT, and for every SSS-TTT path QQQ,

f(P)≥f(Q)(d−1)(r+1).f(P)\ge\frac{f(Q)}{(d-1)(r+1)}.f(P)≥(d−1)(r+1)f(Q)​.

In particular the inequality holds for a reward-maximizing path. Algorithm 5 is defined by the recursive dynamic program, including the full stored-prefix marginal and the singleton base case. This lemma supports Theorem 15; neither its exact ratio nor its runtime is replaced by an assumed field.

Differences from the source:

  • reading: word-RAM operations with input and oracle values fitting a word (footnote 2) → the unchanged published word-charged integer RAM, including its value query and uniform rand M; reason: reuse the accepted base machine model; word length covers input integers and all oracle numerators and denominators, and every RAM run must halt within the bound
  • reading: nonnegative real-valued oracle rewards → nonnegative rational-valued oracle rewards, using the accepted base finite-representation convention; reason: footnote 2 requires finite word representations; no normalization, integral-reward hypothesis or magnitude bound is added
  • encoding: n^{O(r)} runtime and factor 1/((d−1)(r+1)) against an optimal path → one positive absolute integer c and one deterministic RAM program, cost at most (n+1)^{c(r+1)}, with the same exact factor against every feasible path; reason: the maximum exists among finitely many layer-spanning paths, so universal comparison is equivalent; n+1 and r+1 cover n=1 and r=0
  • encoding: induced consecutive-layer blocks, ⊥ and unspecified ties in Algorithm 5 → an offset into the published LGraph, Option paths, strict-improvement updates and increasing-index tie order; reason: the offset restricts every recursive singleton to its own block; each chosen tie is a permitted maximizer; no restriction to singleton endpoints or positive r is made
Preamble
import Mathlib
import Definitions.Def_SubmodMDP_Policies_Supplement_Algorithm5
Formal statement
namespace SubmodMDP.Policies.Supplement

/-- Lemma 14, printed p. 24 (PDF p. 25), including the runtime conclusion.
The same deterministic RAM program implements Algorithm 5 for every d,r and every oracle.
The approximation is stated against every feasible path, equivalently against the maximum. -/
theorem lemma_14 :
    ∃ c : ℕ, 0 < c ∧ ∃ Alg : Program, Alg.Deterministic ∧
    ∀ (G : LGraph), G.WF → ∀ d r : ℕ, 2 ≤ d → G.H = d ^ r →
    ∀ S T : Finset (Fin G.N),
      (∀ v ∈ S, G.layer v = 1) → (∀ v ∈ T, G.layer v = G.H) →
      (∃ P, STPath G S T P) →
    ∀ f : Finset (Fin G.N) → ℚ, Reward f →
    let O : Oracle := ⟨G.N, f⟩
    let inp := encDP G d r S T
    let B := (G.N + 1) ^ (c * (r + 1))
    Computes Alg O (wordLen inp O) inp B (encOptionalWalk (alg5 G d r 0 S T f)) ∧
    ∃ P, alg5 G d r 0 S T f = some P ∧ STPath G S T P ∧
      ∀ Q, STPath G S T Q →
        (f Q.toFinset : ℝ) / (((d : ℝ) - 1) * ((r : ℝ) + 1)) ≤ (f P.toFinset : ℝ) := by sorry

end SubmodMDP.Policies.Supplement
Source
Lars Rohwedder, Rico Zenklusen, STOC 2027 submission #658 (October 2026), Lemma 14 and Algorithm 5, p. 24 (PDF p. 25); proof, p. 25 (PDF p. 26)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me