A Full Feasible Dual Prevents Algorithmic Failure
ProvedPrimalDual.buchbinder_naor_feasible_dual_prevents_failurefailure-certificateload-balancingonline-algorithmsprimal-dualweak-duality
Assume the unrelated-machines packing dual admits a feasible solution assigning unit total mass to every job:
Then the normalized Buchbinder–Naor phase completes without failure and assigns every job to some machine.
This is the failure-certificate half of Theorem 8.1 of the source: a feasible dual that assigns all jobs certifies that the normalized instance is solvable, so the online phase cannot fail. Combined with the machine-load bound it yields the mission's final theorem.
Formalization Note The certificate is not an input to the algorithm; it appears only in the hypothesis. Success is the statement that the run's failure marker is unset, and the assignment of each job is read off the final state.
Preamble
import Definitions.Def_pd_unrelated_machines
Formal statement
namespace PrimalDual
/--
The source failure-certificate argument: weak duality rules out an overweight
failure, while unit dual mass for every job rules out an empty eligible set.
Consequently the normalized phase assigns every job.
-/
theorem buchbinder_naor_feasible_dual_prevents_failure
{jobs machines : ℕ} (I : UnrelatedMachines.Instance jobs machines)
(y : I.EligiblePair → ℝ) (hy : I.DualAssignsAll y) :
I.Succeeded ∧ I.AssignsAll := by
sorry
end PrimalDualSource
Niv Buchbinder and Joseph (Seffi) Naor, The Design of Competitive Online Algorithms via a Primal--Dual Approach, https://www.tau.ac.il/~nivb/download/pd-survey.pdf, Theorem 8.1 and proof of Claim (2), pp. 195--196.