§3, TEST(V), p. 38 — rounding decreases each edge-length by at most Vε/(n − 1) and each path-length by at most Vε
ProvedHassinRSP.Rounding.rounding_errorConsider an instance of the restricted shortest path problem: vertices with , edges with , and positive integer lengths . Let and , and put . TEST(V) replaces each length by , where .
Then for every edge ,
and for every path in (between any two vertices), with the sum of the rounded lengths of its edges,
In the paper's words: "This decreases each edge-length by at most , and each path-length by at most ." The path bound rests on the fact that, because every edge goes from a smaller to a larger vertex, a path has at most edges. Both TEST(V) and the final step of the Rounding Algorithm rely on this error estimate.
Formalization Note. The time bound and the upper bound play no role and are omitted. The path bound is stated for paths between arbitrary vertices, as in the paper's "each path-length".
import Mathlib import Definitions.Def_HassinRSP_Rounding_Setting
namespace HassinRSP.Rounding
theorem rounding_error (I : Instance) (hI : I.WellFormed) (ε : ℝ) (hε0 : 0 < ε)
(V : ℝ) (hV : 0 < V) :
(∀ e ∈ I.E, V * ε / ((I.n : ℝ) - 1) * roundLen I ε V e ≤ I.c e ∧
(I.c e : ℝ) - V * ε / ((I.n : ℝ) - 1) * roundLen I ε V e ≤ V * ε / ((I.n : ℝ) - 1)) ∧
(∀ (i j : ℕ) (p : List ℕ), IsPathIn I.E i j p →
V * ε / ((I.n : ℝ) - 1) * roundPathLen I ε V p ≤ pathLen I p ∧
(pathLen I p : ℝ) - V * ε / ((I.n : ℝ) - 1) * roundPathLen I ε V p ≤ V * ε) := by sorry
end HassinRSP.Rounding
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.