Proof of `Corollary 2`
groundedproofs/Lax496464Proofs/Ram/D4Final.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.
In the paper
- page 4 of this submission's paper
Description
Corollary 2 as a word RAM program. Read the word, sort the jobs by start time, sum the preprocessing times into , and fill the dual table of Section 3 over sets of thresholds written as base- numbers: the numbers are visited from the top, each is decided to be a code of a set or not by a recurrence, and the two sets , of recursion (1) are found by one scan of its digits (, independent of ), after which its cells cost each. The table records, for each instant , the largest weight attainable from , capped at the threshold (so its entries never leave the word); the block of the empty set is zero, and the answer is the entry of the first indices at instant . The sets contribute in all. The domain restricts to positive processing times, the paper's standing assumption for Lemma 1's recursion. The running time is : no work per machine beyond the scan of a set.