2026/07/16 by Dean Matthew Menezes, C. Gregory Plaxton
Computer Science · Mathematics · #cs.DS #math.OC
29 pages, 3 figures
arxiv created 2026/07/30 · arxiv updated 2026/07/31
We revisit the single-machine problem 1||∑ Uj through Moore's shortest-processing-time insertion rule: scan jobs from shortest to longest and accept a job whenever the accepted set remains feasible. Direct implementation checks every affected deadline prefix and takes quadratic time. For job set Y, let \rm Slack(Y) be its least deadline-prefix gap in isolation. A candidate (p,d) is addable to accepted set X if and only if Proc(X<d)+p ≤ mind, \rm Slack(X≥ d). An augmented balanced search tree stores total work and intrinsic slack per subtree, composing under an associative ordered-block product. A read-only query follows a root-to-leaf path: right turns accumulate work due before d; left turns certify d and a skipped suffix. With q stored deadlines, queries and point updates take O(log(q+2)) worst-case time. The scan runs in O(nlog(k+2)) time (k output distinct deadlines) and O(nlog n) overall. Matching algebraic computation-tree lower bounds show O(nlog n) is optimal, persisting when pj=1 under a given SPT order. Preprocessed q-key states still require Ω(log q) per query. For every attainable cardinality, acceptance prefixes over all tie orders are precisely minimum-work feasible sets with componentwise-minimum sorted processing-time vectors. Equal-processing-time choices form canonical chain-presented laminar matroids; their direct sum describes all complete greedy outputs, and their ordered sum describes all optimal prefixes. Finally, a linear-size flow network defines a scheduling polymatroid rank whose contracted, scaled increments recover the complete rank functions of the tier matroids.