§4, p. 39 — a T-path optimal for the scaled costs ⌊c_ij(n − 1)/εLB⌋ is longer than any T-path by at most εLB
ProvedHassinRSP.Rounding.scaled_opt_errorConsider an instance of the restricted shortest path problem (vertices , , edges with , positive integer lengths and transition times), a time budget , and . Let be a -path that is optimal for the scaled lengths
i.e. for every -path (Step 2 of the Rounding Algorithm). Then every -path satisfies
This is the paper's "an -approximation can be obtained by applying Algorithm B to the scaled costs . The error introduced is at most ". Combined with OPT it gives the approximation ratio .
Formalization Note. The estimate holds for any ; the hypothesis that LB is a lower bound on OPT is only needed to turn the additive error into the ratio and is not part of this statement. The upper bound is omitted as unused. The paper's "" is not formalized here; with LB OPT possible it holds only as .
import Mathlib import Definitions.Def_HassinRSP_Rounding_Setting
namespace HassinRSP.Rounding
theorem scaled_opt_error (I : Instance) (hI : I.WellFormed) (T : ℕ) (ε : ℝ) (hε0 : 0 < ε)
(LB : ℝ) (hLB : 0 < LB) (p : List ℕ) (hp : IsRoundingOutput I T ε LB p) :
∀ q, IsTPath I T q → (pathLen I p : ℝ) ≤ pathLen I q + ε * LB := by sorry
end HassinRSP.Rounding
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.