Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 15 — deterministic combinatorial orienteering without a length bound

Open
SubmodMDP.Policies.Supplement.theorem_15

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 finite directed graph with n=∣V∣n=|V|n=∣V∣ and endpoints s,ts,ts,t, and assume some sss-ttt walk exists. Let fff be a nonnegative monotone submodular value oracle, and let OPT\mathrm{OPT}OPT be its maximum reward over all finite sss-ttt walks, with no length bound.

There exist a positive absolute integer ccc and an integer-indexed family of deterministic combinatorial programs such that for every real ε>0\varepsilon>0ε>0 there is Kε>0K_\varepsilon>0Kε​>0, independent of the instance and oracle, for which the program indexed by k=max⁡{1,⌈2/ε⌉}k=\max\{1,\lceil2/\varepsilon\rceil\}k=max{1,⌈2/ε⌉} returns an sss-ttt walk WWW in at most (n+1)ck(n+1)^{ck}(n+1)ck charged operations and

f(W)≥OPTKεnε.f(W)\ge\frac{\mathrm{OPT}}{K_\varepsilon n^\varepsilon}.f(W)≥Kε​nεOPT​.

The program implements the specified polynomial-size general-to-layered reduction, Algorithm 5, and reconstruction along fixed connecting paths. It is deterministic in the published instruction-level sense: no random instruction occurs. No length function, budget, normalized-reward assumption or reward-magnitude bound is part of the input. This companion theorem uses Lemma 14 and is independent of the LP-based MDP goal.

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: arbitrary finite directed s-t walks and their optimum → Mathlib Digraph on Fin n and the maximum over achievable visited sets; reason: walks may repeat vertices and arcs, s=t and zero-length walks are retained; the visited-set family is finite and feasible inputs attain its maximum
  • encoding: O(n^ε) ratio and n^{O(1/ε)} runtime for every ε>0 → K_ε after ε, one absolute exponent c before ε, integer parameter k=max(1,ceil(2/ε)) and cost (n+1)^{ck}; reason: integer and large-ε runtime convention; it is O(1/ε) for 0<ε≤1 and a fixed polynomial for ε≥1; the program family is chosen before ε and never receives a real number
  • encoding: combinatorial algorithm obtained from Algorithm 5 and the general-to-layered reduction → deterministic RAM output is exactly the defined reduction/Algorithm 5/reconstruction result; unit lengths choose only fixed connecting paths; reason: the unit lengths do not constrain output or comparison walks and are not a length bound; the final RAM cost covers all stages
Preamble
import Mathlib
import Definitions.Def_SubmodMDP_Policies_Supplement_Reduction
Formal statement
namespace SubmodMDP.Policies.Supplement

/-- Theorem 15, printed p. 25 (PDF p. 26). The algorithm is deterministic and combinatorial:
it implements the reduction followed by Algorithm 5 and fixed connecting paths. There is no
length function or budget in the input or in the optimum. The cost exponent c is absolute. -/
theorem theorem_15 :
    ∃ c : ℕ, 0 < c ∧ ∃ Alg : ℕ → Program, (∀ k, (Alg k).Deterministic) ∧
    ∀ ε : ℝ, 0 < ε → ∃ Kε : ℝ, 0 < Kε ∧
    ∀ (n : ℕ) (I : Ori n), (∃ W, Walk I.graph I.s I.t W) →
    ∀ f : Finset (Fin n) → ℚ, Reward f →
    let O : Oracle := ⟨n, f⟩
    let inp := encOri I
    let B := polyTime n (epsK ε) c
    Computes (Alg (epsK ε)) O (wordLen inp O) inp B
      (encOptionalWalk (combinatorialWalk I (epsK ε) f)) ∧
    ∃ W, combinatorialWalk I (epsK ε) f = some W ∧ Walk I.graph I.s I.t W ∧
      (optimum I f (fun _ => True) : ℝ) / (Kε * (n : ℝ) ^ ε) ≤ (f W.toFinset : ℝ) := by sorry

end SubmodMDP.Policies.Supplement
Source
Lars Rohwedder, Rico Zenklusen, STOC 2027 submission #658 (October 2026), Theorem 15, p. 25 (PDF p. 26); reduction, p. 14 (PDF p. 15)

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