§4, p. 39 — along the Rounding Algorithm, LB stays a positive lower bound on OPT and UB an upper bound
ProvedHassinRSP.Rounding.rounding_run_boundsConsider an instance of the restricted shortest path problem (vertices , , edges with , positive integer lengths and transition times), a time budget and . Run Step 1 of the Rounding Algorithm from initial bounds , where and every -path has length at least , and let be the bounds after passes: each pass with tests and sets on YES, on NO.
Then for every :
- ;
- every -path satisfies ;
- if some -path has length at most , then some -path has length at most .
This is the paper's "TEST(V) can be applied now to improve the bounds on OPT. Specifically either LB is increased to or UB is decreased to ": the bounds remain valid bounds on OPT throughout the run.
Formalization Note. "LB OPT" is stated as a bound on every -path, and "OPT UB" as the existence of a -path of length at most UB, assumed at the start and concluded at every stage. The hypothesis is not needed and is omitted; is arbitrary.
import Mathlib import Definitions.Def_HassinRSP_Rounding_Setting
namespace HassinRSP.Rounding
theorem rounding_run_bounds (I : Instance) (hI : I.WellFormed) (T : ℕ) (ε : ℝ)
(hε0 : 0 < ε) (LB0 UB0 : ℝ) (hLB0 : 0 < LB0)
(hLB0_le : ∀ q, IsTPath I T q → LB0 ≤ pathLen I q) (k : ℕ) :
0 < (roundingRun I T ε LB0 UB0 k).1 ∧
(∀ q, IsTPath I T q → (roundingRun I T ε LB0 UB0 k).1 ≤ pathLen I q) ∧
((∃ q, IsTPath I T q ∧ (pathLen I q : ℝ) ≤ UB0) →
∃ q, IsTPath I T q ∧ (pathLen I q : ℝ) ≤ (roundingRun I T ε LB0 UB0 k).2) := by sorry
end HassinRSP.Rounding
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.