Proof of `Lemma 5` (1st statement)

groundedproofs/Lax496464Proofs/Section6.lean · lax-496464

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

With a common preprocessing time, the prefix sum of constraint (6) counts the selected jobs up to jj and Condition 1 becomes ∣i≤j∩Z∣≤⌊sj/p⌋|{i ≤ j} ∩ Z| ≤ ⌊s_j/p⌋; constraint (7) is Condition 2 tested at the start times, which is enough by the depth characterization.