Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§4, Rounding Algorithm, p. 39 — once UB ≤ 2LB, a T-path optimal for ⌊c_ij(n − 1)/εLB⌋ has length ≤ (1 + ε)·OPT

Proved
HassinRSP.Rounding.rounding_algorithm_approx

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximation-schemefpasp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1restricted-shortest-pathrounding-and-scaling

Consider an instance of the restricted shortest path problem: a directed graph on vertices 1,…,n1,\dots,n1,…,n (n≥2n\ge2n≥2) whose edges (i,j)(i,j)(i,j) satisfy i<ji<ji<j, with positive integer lengths cijc_{ij}cij​ and transition times tijt_{ij}tij​, a time budget TTT, and a fixed 0<ε<10<\varepsilon<10<ε<1. A TTT-path is a 111–nnn path of transition time at most TTT; OPT is the length of a shortest one.

Run Hassin's Rounding Algorithm:

  1. Step 0: start with bounds LB0>0LB_0>0LB0​>0 and UB0UB_0UB0​, where every TTT-path has length at least LB0LB_0LB0​.
  2. Step 1: while UB>2LBUB>2LBUB>2LB, let V=(LB⋅UB)1/2V=(LB\cdot UB)^{1/2}V=(LB⋅UB)1/2; set LB←VLB\leftarrow VLB←V if TEST(V) = YES and UB←V(1+ε)UB\leftarrow V(1+\varepsilon)UB←V(1+ε) if TEST(V) = NO.
  3. Step 2: when UB≤2LBUB\le 2LBUB≤2LB (say after NNN passes, with lower bound LBNLB_NLBN​), output a TTT-path ppp that is optimal for the rounded lengths ⌊cij(n−1)/(εLBN)⌋\lfloor c_{ij}(n-1)/(\varepsilon LB_N)\rfloor⌊cij​(n−1)/(εLBN​)⌋.

Then the output is a (1+ε)(1+\varepsilon)(1+ε)-approximation: for every TTT-path qqq,

c(p)≤(1+ε) c(q),c(p)\le(1+\varepsilon)\,c(q),c(p)≤(1+ε)c(q),

that is, c(p)≤(1+ε) OPTc(p)\le(1+\varepsilon)\,\mathrm{OPT}c(p)≤(1+ε)OPT.

This is the approximation guarantee of the first fully polynomial approximation scheme of the paper (§3–§4), built on rounding and scaling of the edge lengths together with a geometric search for a lower bound on OPT.

Formalization Note. OPT is expressed through TTT-paths (it is ∞\infty∞ when no TTT-path exists, in which case there is no output path and nothing to prove). TEST(V) is the decision procedure of §3, defined by its answer. The statement covers every stage NNN at which the stopping test UBN≤2LBNUB_N\le2LB_NUBN​≤2LBN​ holds and every Step 2 output; no assumption on UB0UB_0UB0​ is made. The stopping test need not be reached when (1+ε)2>2(1+\varepsilon)^2>2(1+ε)2>2; see the companion statements on termination. Running times are not formalized.

Preamble
import Mathlib
import Definitions.Def_HassinRSP_Rounding_Setting
Formal statement
namespace HassinRSP.Rounding

theorem rounding_algorithm_approx (I : Instance) (hI : I.WellFormed) (T : ℕ) (ε : ℝ)
    (hε0 : 0 < ε) (hε1 : ε < 1) (LB0 UB0 : ℝ) (hLB0 : 0 < LB0)
    (hLB0_le : ∀ q, IsTPath I T q → LB0 ≤ pathLen I q) (N : ℕ)
    (hstop : (roundingRun I T ε LB0 UB0 N).2 ≤ 2 * (roundingRun I T ε LB0 UB0 N).1)
    (p : List ℕ) (hp : IsRoundingOutput I T ε (roundingRun I T ε LB0 UB0 N).1 p) :
    ∀ q, IsTPath I T q → (pathLen I p : ℝ) ≤ (1 + ε) * pathLen I q := by sorry

end HassinRSP.Rounding
Source
Hassin, Approximation schemes for the restricted shortest path problem, Math. Oper. Res. 17 (1992), p. 39, §4, Rounding Algorithm, with Procedure TEST(V) of §3, p. 38
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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