Restricting the Full Dual Witness to a Prefix
ProvedPrimalDual.buchbinder_naor_restrict_dual_throughLet be a feasible dual solution of the unrelated-machines packing dual that assigns unit total mass to every job: , for every machine , and for every job , all sums ranging over eligible pairs. Restrict to the eligible pairs of the first jobs. Then the restriction is feasible for the prefix dual, and its objective equals the number of revealed jobs:
This prefix lemma makes explicit the restriction implicit in the source's weak-duality failure certificate: at the moment of a hypothetical failure after assignments, it supplies a feasible dual of value exactly for the prefix program.
Formalization Note The restriction only forgets pairs with job index ; no values are altered. A job with no eligible machine is incompatible with the unit-mass hypothesis, so the premise already forces every job to have at least one eligible machine.
import Definitions.Def_pd_unrelated_machines
namespace PrimalDual
/--
A full feasible dual assigning every job restricts to a feasible prefix dual,
and its prefix objective is exactly the number of revealed jobs.
-/
theorem buchbinder_naor_restrict_dual_through
{jobs machines : ℕ} (I : UnrelatedMachines.Instance jobs machines)
(y : I.EligiblePair → ℝ) (hy : I.DualAssignsAll y)
(k : ℕ) (hk : k ≤ jobs) :
(I.lpThrough k).DualFeasible (I.restrictDual y k) ∧
(I.lpThrough k).dualObjective (I.restrictDual y k) = (k : ℝ) := by
sorry
end PrimalDual