Explicit Prefix Load Bound for Unrelated-Machine Scheduling
ProvedPrimalDual.buchbinder_naor_machine_load_boundRun the normalized Buchbinder–Naor load-balancing algorithm on the first jobs of an instance with machines and nonnegative normalized loads . For every machine , the normalized load it has received satisfies
The bound is unconditional: it holds at every prefix , and in particular for the assignments retained by a phase that has already failed. This is the explicit form of the machine-load guarantee of Theorem 8.1, Claim (1), of the source, and it supplies the load half of the mission's final theorem.
Formalization Note The assigned load is read off the algorithm's state after processing the first arrivals, so the statement quantifies over all prefixes rather than only the complete run; no success or dual-feasibility hypothesis is assumed.
import Definitions.Def_pd_unrelated_machines
namespace PrimalDual
/--
The multiplicative-weight argument for the load-balancing guarantee. Every reachable prefix,
including the prefix retained by a failed phase, puts normalized load at most
`ln(3m) / ln(3/2)` on each machine.
-/
theorem buchbinder_naor_machine_load_bound
{jobs machines : ℕ} (I : UnrelatedMachines.Instance jobs machines)
(k : ℕ) (hk : k ≤ jobs) :
∀ j, I.assignedLoadThrough k j ≤ I.logarithmicLoadBound := by
sorry
end PrimalDual