§4, Rounding Algorithm, p. 39 — once UB ≤ 2LB, a T-path optimal for ⌊c_ij(n − 1)/εLB⌋ has length ≤ (1 + ε)·OPT
ProvedHassinRSP.Rounding.rounding_algorithm_approxConsider an instance of the restricted shortest path problem: a directed graph on vertices () whose edges satisfy , with positive integer lengths and transition times , a time budget , and a fixed . A -path is a – path of transition time at most ; OPT is the length of a shortest one.
Run Hassin's Rounding Algorithm:
- Step 0: start with bounds and , where every -path has length at least .
- Step 1: while , let ; set if TEST(V) = YES and if TEST(V) = NO.
- Step 2: when (say after passes, with lower bound ), output a -path that is optimal for the rounded lengths .
Then the output is a -approximation: for every -path ,
that is, .
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 -paths (it is when no -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 at which the stopping test holds and every Step 2 output; no assumption on is made. The stopping test need not be reached when ; see the companion statements on termination. Running times are not formalized.
import Mathlib import Definitions.Def_HassinRSP_Rounding_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.