Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — LP-based orienteering in both approximation regimes

Open
SubmodMDP.Policies.Supplement.theorem_1

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∣, endpoints s,ts,ts,t, nonnegative integral arc lengths www, and budget C≥0C\ge0C≥0. Let fff be a nonnegative monotone submodular value oracle on vertex sets. Assume that a budget-feasible sss-ttt walk exists, and let OPT\mathrm{OPT}OPT be its maximum reward. There are positive absolute constants K,c,cPreK,c,c_{\rm Pre}K,c,cPre​, a fixed LP preprocessing program, a logarithmic-regime program, and an integer-indexed family of polynomial-regime programs with both following guarantees.

The logarithmic-regime program outputs an sss-ttt walk on every run, in at most ⌈(n+1)c(log⁡2n+1)⌉(⟨w⟩+1)c\lceil(n+1)^{c(\log_2 n+1)}\rceil(\langle w\rangle+1)^c⌈(n+1)c(log2​n+1)⌉(⟨w⟩+1)c charged operations, and

E[f(W)]≥OPTK(log⁡2n+1),E[w(W)]≤C.\mathbb E[f(W)]\ge\frac{\mathrm{OPT}}{K(\log_2 n+1)},\qquad \mathbb E[w(W)]\le C.E[f(W)]≥K(log2​n+1)OPT​,E[w(W)]≤C.

For every real ε>0\varepsilon>0ε>0 there is Kε>0K_\varepsilon>0Kε​>0, independent of the instance and oracle, such that the polynomial-regime program with integer parameter k=max⁡{1,⌈2/ε⌉}k=\max\{1,\lceil2/\varepsilon\rceil\}k=max{1,⌈2/ε⌉} outputs an sss-ttt walk on every run, in at most (n+1)ck(⟨w⟩+1)c(n+1)^{ck}(\langle w\rangle+1)^c(n+1)ck(⟨w⟩+1)c charged operations, and

E[f(W)]≥OPTKεnε,E[w(W)]≤C.\mathbb E[f(W)]\ge\frac{\mathrm{OPT}}{K_\varepsilon n^\varepsilon},\qquad \mathbb E[w(W)]\le C.E[f(W)]≥Kε​nεOPT​,E[w(W)]≤C.

Both programs implement the published constrained LP interface at fixed accuracy δ=1/2\delta=1/2δ=1/2, followed by an independent RRR sample and reconstruction. Their full expectation additionally satisfies the proof's exact bound

E[f(W)]≥(1−N−2)/2(d−1)(r+1) OPT,\mathbb E[f(W)]\ge\frac{(1-N^{-2})/2}{(d-1)(r+1)}\,\mathrm{OPT},E[f(W)]≥(d−1)(r+1)(1−N−2)/2​OPT,

where NNN is the number of reduced vertices and d,rd,rd,r are the specified reduction parameters. Every preprocessing outcome is LP-feasible; the expectation includes unsuccessful reward-preprocessing runs. The cost includes graph construction, shortest paths, oracle simulation, preprocessing, sampling and reconstruction. This companion result supplies the paper's LP-based directed-walk approximation, separately from its MDP policy 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: arbitrary nonnegative real budget C → the effective integer budget floor C, then internally clipped to Hn max_a w(a); reason: integer walk lengths make feasibility and the expected-budget conclusion equivalent to or stronger than the real-budget statement; zero budget and zero arc lengths remain allowed
  • encoding: logarithmic regime O(log n), n^{O(log n)}⟨w⟩^{O(1)}, and the proof transfer factor → absolute K,c,cPre before all instances; ratio K(log₂ n+1), cost ceil((n+1)^{c(log₂ n+1)})(⟨w⟩+1)^c, and the exact proof factor with δ=1/2; reason: the shifts include n=1; fixing δ independently of ε gives (1−N^{-2})/2 and hence at least 3/8 for N≥2; the preprocessing contract and equality of full output laws give the LP-based clause formal content
  • 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
Preamble
import Mathlib
import Definitions.Def_SubmodMDP_Policies_Supplement_Pipeline
Formal statement
namespace SubmodMDP.Policies.Supplement

/-- Theorem 1, printed p. 1 (PDF p. 2), proof printed p. 14 (PDF p. 15).
Both regimes use the same constrained LP preprocessing contract at δ=1/2, followed by an
independent RRR sample and reconstruction. c and the logarithmic ratio constant are absolute;
only the polynomial ratio constant depends on ε. -/
theorem theorem_1 :
    ∃ c cPre : ℕ, 0 < c ∧ 0 < cPre ∧ ∃ K : ℝ, 0 < K ∧
    ∃ Pre AlgLog : Program, ∃ AlgPoly : ℕ → Program,
    (∀ (n : ℕ) (I : Ori n) (w : Fin n → Fin n → ℕ) (C : ℕ),
      (∃ W, Walk I.graph I.s I.t W ∧ walkLength w W ≤ C) →
      ∀ f : Finset (Fin n) → ℚ, Reward f →
        LPGuarantee AlgLog Pre cPre I 2 (logDepth n) w C
          (logTime n c * (sizeW I w + 1) ^ c) f (K * (Real.logb 2 n + 1))) ∧
    (∀ ε : ℝ, 0 < ε → ∃ Kε : ℝ, 0 < Kε ∧
      ∀ (n : ℕ) (I : Ori n) (w : Fin n → Fin n → ℕ) (C : ℕ),
        (∃ W, Walk I.graph I.s I.t W ∧ walkLength w W ≤ C) →
        ∀ f : Finset (Fin n) → ℚ, Reward f →
          LPGuarantee (AlgPoly (epsK ε)) Pre cPre I (polyDegree n (epsK ε))
            (polyDepth n (epsK ε)) w C
            (polyTime n (epsK ε) c * (sizeW I w + 1) ^ c) f (Kε * (n : ℝ) ^ ε)) := by sorry

end SubmodMDP.Policies.Supplement
Source
Lars Rohwedder, Rico Zenklusen, STOC 2027 submission #658 (October 2026), Theorem 1, p. 1 (PDF p. 2); proof, 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