Maintained Prefix Primal Feasibility
ProvedPrimalDual.buchbinder_naor_primal_feasible_throughConsider the normalized Buchbinder–Naor load-balancing algorithm after a successful prefix: it has processed the first jobs and its failure marker is unset. Then the current machine weights and job slacks form a feasible solution of the covering primal restricted to those jobs: all coordinates are nonnegative, and
for every eligible pair with .
This is the maintained primal feasibility from Theorem 8.1, Claim (2), of the source. Together with the exact primal-objective identity and weak duality, it produces the failure certificate that drives the mission's final theorem.
Formalization Note Feasibility is stated for the prefix linear program whose constraints are exactly the eligible pairs revealed so far; the slack coordinates of jobs that have not yet arrived are retained (at value ) and are subject only to nonnegativity.
import Definitions.Def_pd_unrelated_machines
namespace PrimalDual
/--
After every successful prefix, the online load-balancing updates give a feasible covering
solution for exactly the eligible constraints revealed in that prefix.
-/
theorem buchbinder_naor_primal_feasible_through
{jobs machines : ℕ} (I : UnrelatedMachines.Instance jobs machines)
(k : ℕ) (hk : k ≤ jobs)
(hNoFailure : (I.runPrefix k).failedAt = none) :
I.PrimalFeasibleThrough k (I.runPrefix k) := by
sorry
end PrimalDual