Proof of `Day-Independent Processing Times` (2nd statement)
groundedproofs/Lax117284Proofs/Theorem2_UnitP.lean · lax-117284
What this proof establishes
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 2 of this submission's paper
Description
With unit processing times, a fair schedule exists exactly when a bipartite graph has a matching that saturates its left side. The left vertices of the graph are the jobs, one for every day and client. The right vertices are the pairs of a day and a client, of which the first client of a day with a given due date stands for that due date, and, for every client, the days that the client must be served on being taken out of the days, rejection vertices. The graph is written as a flat table of zeros and ones by a word RAM program on the zeros and ones of the word of the instance, in time polynomial in the size of the word; a second word RAM program converts the table into the compressed sparse row word of the graph, in time polynomial in the size of the table; and the cited decider of () decides whether the graph has such a matching in time polynomial in the size of that word. A word that encodes no instance with unit processing times is sent to a graph with one left vertex and no right vertex.