Exact Primal Accounting Identity
ProvedPrimalDual.buchbinder_naor_primal_objective_identityAfter a successful prefix of jobs of the normalized Buchbinder–Naor load-balancing algorithm — the failure marker is unset — the covering-primal objective of the current state satisfies the exact identity
where denotes the current machine weights and the sums over range over all machines.
The identity replaces the source's asymptotic accounting with an exact equation: since every machine weight is positive, it forces as soon as some weight exceeds , which is exactly what the failure certificate needs. It corresponds to the primal-objective calculation in the proof of Theorem 8.1, Claim (2).
Formalization Note The objective on the left is the full finite-LP objective, so it also sums the slacks of jobs with indices ; along the algorithm's run these remain , so the identity coincides with the source's prefix objective.
import Definitions.Def_pd_unrelated_machines open scoped BigOperators
namespace PrimalDual
/--
The telescoping identity used in the failure argument. For a successful prefix
of `k` jobs, `P = 1 + k - sum_j x(j)` exactly (not asymptotically).
-/
theorem buchbinder_naor_primal_objective_identity
{jobs machines : ℕ} (I : UnrelatedMachines.Instance jobs machines)
(k : ℕ) (hk : k ≤ jobs)
(hNoFailure : (I.runPrefix k).failedAt = none) :
I.primalObjectiveThrough k (I.runPrefix k) =
1 + (k : ℝ) - ∑ j, (I.runPrefix k).weight j := by
sorry
end PrimalDual