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

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.

Read the Lean proof on GitHub

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 kk days that the client must be served on being taken out of the mm days, m−km - k 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 lax−817977lax-817977 (ramPolytimesaturatingramPolytime_saturating) 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.