While this submission is a draft, it cannot be used by other submissions.

Proof of `Construction 1` (2nd statement)

groundedproofs/Lax470956Proofs/Construction1Emit.lean · lax-470956

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

The layout is the archive's, discharged once and generically in EncoderEncoder: the two counts, one entry per job for each of the processing times, deadlines and weights, the n+1n + 1 offsets, and the eligibility lists run together. What is about this construction is only that every machine number it lists is a machine — the validation machine is C(k,2)C(k,2) and the edge selection machines are numbered below it by pairIdxpairIdx, which Construction1IndexConstruction1Index shows lands exactly in [0,C(k,2))[0, C(k,2)).

The word is the instance followed by the threshold, as a decision instance is.