Test or Run? Scheduling Jobs of Unknown Length

1 Introduction

• Hidden-length scheduling balances learning which jobs are short against completing jobs, since each test delays all unfinished jobs and shortest-first is optimal with full information.The paper studies variants where testing reveals lengths, improves running times, or provides both benefits.Source: §1 · p. 3

1.1 Warmup: every job has to be tested

• In obligatory testing, the optimal asymptotic competitive ratios are 1.57... deterministically and 4/3 against an oblivious adversary, closing previous deterministic gaps and the randomized open case.Both optimal algorithms use shortest-first execution after threshold-based testing decisions.Source: §1.1 · p. 3

Algorithm 1

• The deterministic algorithm adapts its threshold to testing history, whereas randomization estimates the job-length distribution from a sublinear shuffled sample and uses one fixed threshold.Both algorithms process short jobs immediately and defer long jobs for shortest-first completion; the randomized threshold minimizes expected work per immediate completion.Source: Algorithm 2 · pp. 4–5

1.2 One algorithm for every bounded input multiset

• For every fixed upper bound L, the randomized obligatory-testing threshold algorithm is instance-optimal on every input, even against an algorithm tailored to that input and told its lengths.The fixed-bound and randomization assumptions are necessary, and the optimal algorithm remains simple rather than requiring a separate meta-algorithm.Source: §1.2 · p. 5

1.3 Generalizations of the model

• The paper separates blind execution, blind optimization, and revealing optimization, while randomized algorithms in all optional models privately shuffle jobs, sample sublinearly, and optimize schedules using the estimated distribution.The models differ in whether the preliminary action provides information, speedup, or both.Source: §1.3 · pp. 5–6

1.4 Information without speedup: blind execution

• For blind execution, no randomized algorithm has finite competitive ratio without a length bound, but for every fixed L one sampled algorithm is instance-optimal and may stop testing before all jobs.It processes deferred jobs below the estimated mean before running untouched jobs blindly, choosing the tested fraction by minimizing an explicit quadratic.Source: §1.4 · pp. 6–7

1.5 Blind optimization

• In blind optimization, hard inputs yield Θ(n^2√u) online cost versus Θ(n^2) clairvoyant cost, while randomization halves the asymptotic worst-case ratio and a sampled algorithm is instance-optimal for every fixed u.The instance-optimal algorithm chooses between optimizing every job and optimizing none at leading n^2 scale.Source: §1.5 · pp. 7–8

1.6 Revealing optimization

• For revealing optimization, the exact deterministic and randomized ratios follow six-piece and four-piece curves: deterministic peaks at 1.86... before reaching 1.57..., while randomized peaks at 1.62... before reaching 4/3.The deterministic curve uses three explicit algorithm families over consecutive u-ranges, including a forced-prefix threshold strategy against long-job-first adversaries.Source: §1.6 · pp. 8–10
• The deterministic algorithms Raw, ForcedPrefixUTE, and AdaptiveThreshold trace the curve in Figure 1, while one randomized instance-optimal algorithm defines the curve in Figure 2.For every fixed 0 < u < ∞, the randomized algorithm A∗ satisfies E ALG A∗ ≤ E ALG A′ + o_u(n^2) for every online algorithm A′.Source: Algorithm 5 · p. 10

Algorithm 6

• Revealing and blind optimization quantify advance information: revealing ratios remain bounded as u grows, whereas blind ratios grow as Θ(√u).The revealing-optimization curves are nonmonotone because testing is useless for very small u, while intermediate values give raw execution additional options.Source: Algorithm 6 · pp. 10–11

1.7 Techniques

• The proofs use remaining-job and pair accounting, completion-density ordering of algorithmic modules, and private shuffling to estimate distributions and justify a fluid model.Pair accounting makes parameter optimization quadratic in test fractions, while private shuffling keeps the remaining-job distribution close to the estimate.Source: §1.7 · p. 11

1.8 Related work

• Relative to prior work, the paper contributes matching revealing-optimization bounds, exact per-u curves, improved deterministic guarantees, and a general instance-specific fluid characterization.For obligatory testing, its matching value is 1.57... and its randomized oblivious value is 4/3, with asymptotic optimality for every bounded input [LL26].Source: §1.8 · p. 12

1.9 Roadmap

• The roadmap develops fluid instance-optimal benchmarks, exact deterministic and randomized revealing curves, obligatory endpoints, and deterministic and randomized blind-optimization curves.The paper also states that all main exact-ratio, instance-optimality, and impossibility results were proved in Lean 4.Source: §1.9 · p. 13

2 Models and common preliminaries

• Together, these preliminaries reduce later analyses to model-specific effective lengths, information constraints, asymptotic benchmarks, and concentration control under shuffled or predictable sampling.The common fluid problem is deferred to Section 3.Source: §2 · p. 13, §2.1 · p. 14, §2.2 · p. 14

2.1 Models

• The four models vary whether jobs are tested, run blindly, or optimized before execution, with preliminary actions costing one unit and hidden lengths p_j revealed model-dependently.All jobs are initially available, operations are nonpreemptive, and the machine runs at most one operation at a time.Source: §2.1 · p. 13

2.2 Input, information and adversaries

• Randomized analyses use an oblivious adversary and a private uniform shuffle, while instance-optimal algorithms compare one unannounced algorithm with announced competitors at leading n^2 scale.Announced algorithms know the multiset but not its label assignment; unannounced algorithms know only public parameters, and lower bounds use finite one-sided Yao’s principle.Source: §2.2 · pp. 14–15

2.3 Offline optima and pair accounting

• For every model, the clairvoyant optimum executes each job using its shortest feasible effective length and orders jobs by nondecreasing effective length.Lemma 2.1 gives the resulting offline pair identity, with effective lengths 1 + p_j in OT, p_j in BE, and min{u, 1 + p_j} in BO(u) and RO(u).Source: §2.3 · p. 15

2.4 Competitive-ratio conventions

• Competitive ratios are defined up to a uniform additive o(n^2) term as n grows with model parameters fixed, but blind execution instead requires an absolute benchmark when OPT can be o(n^2).In obligatory testing and optimization, OPT = Ω(n^2); the blind-execution theorem uses E ALG = n^2Φ_BE(D[p]) + o_L(n^2) and does not assert a bounded clairvoyant ratio for mostly zero jobs.Source: §2.4 · p. 16

2.5 Concentration and predictable sampling

• The randomized toolkit combines Chernoff, sampling-without-replacement, histogram, martingale, and predictable-sampling bounds to control fixed and adaptive prefixes uniformly.Predictable sampling permits data-dependent weights selected before each draw and remains valid after conditioning on independent private randomness.Source: §2.5 · pp. 17–18

• The same fluid-model analysis proves instance-optimality for revealing optimization, obligatory testing, and blind execution.The section first solves the fluid model exactly, then shows its value gives the leading cost on every bounded input.Source: §3 · p. 19
• Privately shuffling job values makes a tested prefix reveal approximately the same fraction of every processing-time class as of the full input.If the algorithm tests fraction t of all jobs, it sees approximately fraction t of each class, despite adaptively choosing the prefix length from observed jobs.Source: §3 · p. 19
• The fluid model replaces n jobs with one unit of divisible mass, makes class proportions exact, and describes the leading n^2 term of total completion time.Testing mass 0.01 reveals exactly a 0.01 copy of the input distribution; the approximation to shuffled jobs is proved later.Source: §3 · p. 19

3.1 The fluid model

• A fluid schedule uses finitely many divisible blocks: testing blocks select revealed positive types and defer the rest, while deferred and alternative-completion blocks finish jobs.Testing mass is limited by q, alternative completion by 1−q, and a complete schedule eventually empties every deferred queue.Source: §3.1 · p. 19
• Every finite fluid schedule induces a piecewise-linear completion curve, and total completion cost equals the area of unfinished mass under that curve.Continuous work is a coordinate for the curve; the schedule itself still consists of finitely many block decisions.Source: §3.1 · p. 20, Figure 3 · p. 20
• The maximum-density testing block selects every positive type below a unique threshold τ_D, rejects types above it, and may fractionally select the threshold type.Its completion density is 1/τ_D, with w* = τ_Da*; deferred types therefore require at least as much work per completion as the testing block.Source: §3.1 · p. 21
• After testing is compressed into one block, divisible completion blocks minimize cost when processed in nondecreasing order of work per completion.The shortest-first ordering follows by exchanging adjacent blocks, with the area change nonpositive whenever the earlier block has lower work per completion.Source: §3.1 · pp. 21–22

3.2 The optimal fluid schedule

• Every schedule is represented by aggregate tested mass, alternative-completed mass, and processed positive mass satisfying a finite-dimensional envelope.The state obeys 0 ≤t ≤q, 0 ≤b ≤1 −q, and 0 ≤ci ≤dit.Source: §3.2 · p. 22, Algorithm 7 · p. 23

Algorithm 7

• The explicit schedule computes a maximum-density selector, creates testing, deferred, and alternative-completion blocks, and orders all nonempty blocks by nondecreasing work per completion.The testing block precedes deferred blocks on ties.Source: Algorithm 7 · p. 22
• FluidSPT(D, q, v) matches the envelope at every work budget, completing at least as much mass as any feasible fluid schedule and minimizing fluid total completion time.The result follows by integrating the pointwise inequality.Source: Algorithm 7 · pp. 23–24
• The envelope proof replaces all testing activity with one maximum-density block, leaving independent deferred and alternative blocks that are optimally executed shortest first.This construction realizes the envelope simultaneously for every work budget.Source: Algorithm 7 · pp. 23–24
• The framework covers obligatory testing with q = 1, revealing optimization with v = u, and blind execution with v = µD, but not blind optimization.For revealing and blind execution, q is chosen from [0, 1].Source: Algorithm 7 · p. 24

3.3 From fluid schedules to finite inputs

• Theorem 3.7 transfers the fluid optimum to finite inputs: a randomized nonanticipating learner achieves the fluid cost asymptotically, while every such algorithm is bounded below by it.The upper bound learns the empirical distribution from a sublinear sample and runs the corresponding fluid algorithm in finite batches; the lower bound applies even when the input multiset is revealed.Source: §3.3 · pp. 24–25

3.3.1 Lower bound: comparing a finite run with the fluid curve

• The lower-bound proof converts an adaptive finite run into a feasible fluid schedule by exploiting random first-touch order, rounding job lengths, concentration, suffix editing, and rounding stability.Predictable-permutation estimates control tested classes and direct work, while zero-preserving rounding stability compares the empirical rounded distribution with the original one.Source: §3.3.1 · pp. 25–27

3.3.2 Upper bound: learning the fluid algorithm

• The upper-bound learner privately samples jobs, constructs a rounded histogram, selects a canonical full-grid minimizing plan, and applies it nonanticipatingly to the remaining jobs.Fixed-plan implementation and stability control finite-population, histogram, and rounding errors, yielding the finite-to-fluid upper inequality uniformly over inputs.Source: §3.3.2 · pp. 27–29

3.4 Revealing-optimization instance optimality

• Theorem 3.14 establishes randomized nonanticipating algorithms that are instance-optimal up to ε_u(n)→0 for every fixed u>0, with a converse lower bound applying even to announced algorithms.The guarantees hold uniformly for every input p∈[0,u]^n.Source: §3.4 · p. 29

3.4.1 The revealing benchmark

• The revealing benchmark uses the common fluid model with v=u, because every untested job runs for the public time u independently of its hidden processing time.For τ_D<u, the schedule consists of testing, residual jobs in shortest-processing-time order, and the raw block; for τ_D≥u, pure raw execution dominates any positive tested fraction.Source: §3.4 · p. 29, §3.4.1 · p. 30
• The benchmark objective is a quadratic in the tested fraction q, whose minimizing choice is q*=1 when B=0 and q*=min{1,−A/(2B)} when B>0.Convex mixing makes the completion envelope concave in q and the unfinished-mass area convex, ensuring B≥0.Source: §3.4.1 · p. 30

3.5.1 The obligatory benchmark

• With obligatory testing, the optimal fluid schedule is the maximum-density testing block followed by a deferred SPT tail, and its value is attainable up to O_L(n).The benchmark proof shows no other fluid schedule has smaller cost, while the finite implementation reaches the fluid value up to O_L(n) when the multiset is announced.Source: §3.5 · p. 30, §3.5.1 · p. 31

3.5 Obligatory-testing instance optimality

• A single randomized nonanticipating algorithm depending only on n is asymptotically instance-optimal uniformly over every bounded input class, with ε_L(n)=O_L(n^-1/5).The guarantee holds for every fixed L<∞ and every input p∈[0,L]^n.Source: §3.5 · p. 31, Algorithm 8 · p. 33

Algorithm 8

• Algorithm 8 learns the schedule without knowing the input bound by privately sampling, rounding values to a growing grid, selecting a maximum-density prefix, and deferring the remaining jobs to SPT.Its cutoff tends to infinity and its grid mesh tends to zero; overflow values are never selected, and closure protects against unseen short values.Source: §3.5.2 · p. 32, Algorithm 8 · p. 32

3.5.3 Why randomization and boundedness are necessary

• Deterministic instance optimality is impossible even for lengths in [0,2], whereas an announced randomized algorithm avoids the deterministic lower-bound construction.The theorem gives a fixed labeling with n/2 zero jobs and n/2 length-two jobs for every deterministic algorithm.Source: §3.5.3 · p. 33
• Without a fixed bound on processing times, no randomized instance-optimal algorithm achieves one uniform additive o(n^2) term.For every sufficiently large n, an input with values in [0,n^2] defeats any randomized algorithm independent of the input.Source: §3.5.3 · p. 33

3.6.1 The four-block benchmark

• The four-block benchmark orders maximum-density testing, tested medium jobs, blindly executed jobs, and tested long jobs; when τ_D < µ, the order is tested jobs, blind execution, then tested residuals.If τ_D ≥ µ, pure blind execution is optimal with cost µ/2; otherwise the tested fraction is optimized from the quadratic completion-area expression.Source: §3.6 · p. 34, §3.6.1 · pp. 35–36

3.6 Blind-execution instance optimality

• Theorem 3.19 establishes randomized nonanticipating algorithms achieving blind-execution instance optimality on every input p ∈ [0, L]^n, with a converse applying even when the length multiset is known.The benchmark Φ_BE is defined explicitly, and the approximation error vanishes through a deterministic sequence ε_L(n) → 0.Source: §3.6 · p. 35

3.6.2 An example requiring all four blocks

• An example has µ = 57/5, τ_D = 5, optimal tested fraction q* = 4/5, and value 1249/250, whereas deferring all tested residuals yields 126/25.The positive constant-scale gap shows that the simpler order “testing block, blind block, all tested residuals” is not instance optimal.Source: §3.6.2 · p. 36

3.6.3 Unbounded processing times

• Without a finite upper bound on processing times, no randomized algorithm can achieve a finite worst-case ratio for blind execution.Changing one uniformly selected zero-length job to length H = n^2 creates an input whose online cost contradicts any finite-ratio guarantee for sufficiently large n.Source: §3.6.3 · p. 37

Theorem 4.1

• Theorem 4.1 gives the optimal deterministic revealing-optimization ratio for every finite u as six formulas separated by five transition points.The curve uses positive-root characterizations where needed; notable transition values include 3.14..., 3.61..., and 4.50....Source: §4 · pp. 37–38
• Explicit deterministic algorithms attain the curve on every interval with an additive O(n) term, while matching lower bounds hold on arbitrarily large instances.The upper-bound witnesses are raw execution, a forced-prefix uniform threshold, and a history-dependent adaptive threshold; lower bounds use binary hidden-stopping and continuous harmonic constructions.Source: §4 · pp. 38–39

Endpoint uniformity

• The lower-bound witnesses on the plateau can be chosen with p_j < u − 1 for every job, so the offline cap is inactive and the endpoint passage is uniform.This uniformity supports taking the finite-u result separately to the obligatory-testing endpoint.Source: §4 · p. 38

Theorem 4.2

• Theorem 4.2 identifies u_det5 as the unique endpoint parameter and proves that every deterministic obligatory-testing algorithm has the corresponding lower bound on arbitrarily large instances.The theorem also supplies a deterministic algorithm with an absolute additive Bn upper bound, making the optimal size-asymptotic ratio exact.Source: §4 · p. 39

4.1 Upper bounds

• Three algorithms establish guarantees across the six intervals, with raw execution covering the initial range and forced-prefix uniform thresholds covering subsequent ranges.Each algorithm is analyzed separately and ends with its complete guarantee on the relevant interval.Source: §4.1 · p. 39

4.1.1 Raw execution

• Raw execution is optimal for u ≤1 and remains u-competitive until the first nontrivial transition point udet.It executes each job untested for u time, yielding ALGRaw = un(n + 1)/2.Source: §4.1.1 · p. 39, Algorithm 9 · pp. 39–40

4.1.2 Forced-prefix uniform thresholds

• ForcedPrefixUTE tests every job, immediately processes forced-prefix jobs and short suffix outcomes, and queues other suffix jobs for nondecreasing revealed processing time.The algorithm uses k = ⌊bn⌋ forced-prefix positions and threshold θu = min{1, u −1}.Source: §4.1.2 · p. 40, Algorithm 10 · p. 40

Algorithm 10

• For u in the analyzed interval, ForcedPrefixUTE satisfies ALG ≤ R · OPT + O_u(n), with an admissible parameter b and positive root R.The proof establishes the guarantee below and above u = 2, using different reductions while retaining the same asymptotic bound.Source: Algorithm 10 · pp. 40, 41, 43
• The ForcedPrefixUTE proof reduces worst cases to structured endpoint or binary instances, orders long or capped jobs adversarially, and verifies the resulting gap is nonpositive.For lower ranges, randomized rounding preserves or increases the online comparison while not increasing expected OPT; for higher ranges, convexity reduces values to endpoints.Source: Algorithm 10 · pp. 42–43
• Algorithm 10 proves its reduced-configuration inequality for every configuration, with only O_u(n) additional cost from restoring one-job terms and rounding.Its parameter guarantees hold throughout the specified interval, and the zero-prefix analysis reduces instances to four job types; binary instances attain the stated bound.Source: Algorithm 10 · pp. 45–46

4.1.3 Adaptive thresholds for the final two parameter intervals

• Algorithm 11 uses a history-dependent threshold based on deferred jobs and positive revelations, processing jobs immediately below it and queueing larger revealed values.The same algorithm covers both final parameter regimes, does not use raw execution, and processes queued jobs in nondecreasing revealed-time order.Source: §4.1.3 · p. 46, Algorithm 11 · p. 47

Algorithm 11

• AdaptiveThreshold satisfies (1 + c) · OPT + O_u(n) for every finite u in the stated middle and high parameter range, with a uniform additive constant.These bounds imply upper bounds on the deterministic size-asymptotic competitive ratio.Source: Algorithm 11 · p. 47
• The Algorithm 11 proof reduces inputs to five endpoint types, allocates pair charges locally, and controls them with a nonnegative potential whose directional derivatives telescope.The reduction fixes a decision transcript, while separate accounting handles cap-valued jobs and the base potential handles types Z, E, M, and Q.Source: Algorithm 11 · pp. 48–50
• The reserve potential Wcap makes the full potential nonnegative and cancels the extra positive charge generated by endpoints of type U.For other endpoint types, the reserve term can only decrease the directional-derivative bound; for type U, its derivative exactly cancels the extra charge.Source: Algorithm 11 · pp. 52–53
• The full potential is initially calibrated at exactly Winitial = cn^2/2, canceling the constant pairwise term.This calibration follows from the definitions and Equations (95) and (148).Source: Algorithm 11 · p. 53
• Regularity and telescoping ensure that every finite transition has a uniformly bounded Taylor remainder, with the bound independent of u in the uniform regime.The potential has a Lipschitz gradient on reachable states, and the endpoint E = 0+ case transfers by a limiting argument without asymptotic loss.Source: Algorithm 11 · pp. 54–55
• Claims 4.10–4.15 combine local charge bounds, potential derivative inequalities, initial calibration, and transition telescoping to yield both displayed finite bounds.The proof uses the potentials from Claims 4.12 and 4.13 and the initial value from Claim 4.14 before applying Claim 4.15.Source: Algorithm 11 · p. 55
• Because every effective offline length is at least one, OPT ≥ n(n + 1)/2, so additive terms vanish in size-asymptotic ratios and the final assertion follows.The lower bound on OPT makes the additive finite-bound terms negligible as n grows.Source: Algorithm 11 · p. 55

4.2 Lower bounds

• The lower bounds combine a hidden binary stopping game with scaled harmonic constructions, including obligatory-testing instances when the offline cap is inactive.The constructions cover different ranges of u; for sufficiently large u, every job satisfies 1 + p_j < u.Source: §4.2 · p. 55

4.2.1 The binary stopping game and its piecewise lower bound

• Binary instances with p_j ∈ {0, u} give a piecewise lower bound for deterministic algorithms, and the stopping point must remain hidden.The adversary records the adaptive interaction as a fixed binary instance, and the construction establishes all four formulas in Equation (179).Source: §4.2.1 · pp. 55, 57

4.2.2 The harmonic construction for short jobs

• The harmonic construction uses equally sized positive-job groups revealed from longest to shortest, followed by zero jobs, with harmonic gaps making the leading term independent of algorithmic decisions.Its extremal theorem applies to every deterministic online algorithm on arbitrarily large fixed instances, and the reveal order can be converted into a fixed input.Source: §4.2.2 · p. 59
• The harmonic construction yields a limiting lower-bound ratio whose global maximum is 1.12…, with the maximizing parameter satisfying α < e −1.The construction sets ξ = K/α, derives the limiting ratio as a one-variable function, and proves the derivative changes from positive to negative at a unique maximizer.Source: §4.2.2 · pp. 63–64
• Scaled harmonic instances provide lower-bound cores with sMν + o(Mν) jobs, normalized positive processing time determined by t, and largest processing time converging to 1 + ln t < 2.The construction works for every s > 0 and t ∈[1, e), and adaptive revelations can be frozen into fixed rational instances.Source: §4.2.2 · p. 64

4.2.3 Combining jobs with p = u and a harmonic block

• Combining a p = u prefix with a later harmonic block prevents early processing of prefix jobs from reducing the leading online cost when every later job satisfies 1 + p ≤u.The quota adversary also accommodates raw execution, preserving the sign of the later block’s excess when R ≤u and D ≥0.Source: §4.2.3 · pp. 65–66
• Every deterministic revealing algorithm has size-asymptotic competitive ratio at least 1 + c(u) under the combined construction.The ratio depends on the prefix fraction m and harmonic parameter t; the stationary equations determine a unique feasible parameter triple, with finite blocks satisfying 1 + p < u.Source: §4.2.3 · pp. 67–68
• For u in the interior range, fixed finite instances force every deterministic revealing algorithm toward ratio 1 + c(u).The construction combines jobs with p = u and a harmonic block, using rational approximations and diagonalization to obtain arbitrarily large finite instances.Source: §4.2.3 · pp. 68–69
• The same lower-bound curve holds at both endpoints: the lower endpoint uses the binary construction, while the upper endpoint follows from the obligatory bound 1 + r = 1 + c(udet 5).No continuity argument between models is used at either endpoint.Source: §4.2.3 · p. 69

4.2.4 Transferring the lower bound when raw execution is no shorter

• Any revealing algorithm with raw-execution cap u induces an obligatory-testing algorithm on instances with 1 + p_j ≤ u without changing transcript comparisons or the offline optimum.The simulation tests and immediately processes a job whenever the virtual revealing algorithm would run it raw for u time, while hiding the answer from the virtual copy.Source: §4.2.4 · pp. 69–70
• The simulation implies that every revealing algorithm’s worst-case ratio is at least LOT(u − 1), and finite constructions also establish the equality case u = 1 + 1/r.The latter uses harmonic instances whose largest processing time approaches 1/r from below.Source: §4.2.4 · p. 70

4.3 Assembly of the curve

• The six candidate formulas are assembled by verifying their shape, exact joins, and matching upper and lower bounds.The resulting curve is transferred to obligatory testing after these consistency checks.Source: §4.3 · p. 70

4.3.1 Shape of the candidate curve

• Rdet RO(u) is globally maximized at u = udet 5 because each relevant formula is strictly decreasing on its interval.The proof establishes strict decrease for Rquad(u), 1 + 1/√u −1, and 1 + c(u) across their respective ranges.Source: §4.3.1 · p. 70

4.3.2 Exact joins and completion of the proof

• The six formulas in Equation (96) agree at all five transition points, so the matched interval bounds prove Theorem 4.1.The proof covers the upper and lower bounds across the intervals, retains the stated O_u(n) remainders and uniform O(n) plateau error, and excludes the unbounded obligatory endpoint from this curve.Source: §4.3.2 · p. 71

4.4 The obligatory endpoint

• The transfer works because the revealing and obligatory offline optima coincide when every effective length satisfies min{u, 1 + p_j} = 1 + p_j.The finite curve already established uniformity in u, so the endpoint is obtained without formally substituting u = ∞.Source: §4.4 · pp. 71–72
• Theorem 4.2 transfers the revealing-model bounds to the obligatory model, yielding the claimed deterministic inequality with an additive term independent of u.For the upper bound, AdaptiveThreshold with c = r never runs a job raw and is independent of u; for the lower bound, obligatory algorithms are viewed as revealing algorithms with a fixed cap.Source: §4.4 · p. 72
• The lower bound applies on instances with p_j below the fixed cap, where raw execution is inactive and the online transcript and offline optima remain unchanged.This yields the obligatory lower bound for arbitrarily large instances.Source: §4.4 · p. 72

5 Randomized revealing optimization: the exact four-piece curve

• Theorem 5.1 establishes the optimal randomized size-asymptotic competitive ratio against an oblivious adversary as a four-piece curve for every fixed u > 0.The proof also supplies matching lower bounds for every randomized online algorithm.Source: §5 · p. 72

The curve is continuous and has global maximum

• Two one-variable maximizations produce the four formulas: flattening the survival function reduces distributions to two-point supports, while shuffled binary inputs provide matching lower bounds.The full curve is displayed in Figure 4.Source: The curve is continuous and has global… · p. 73, Figure 4 · p. 73

5.1 Offline and stationary fluid coefficients

• The stationary algorithm tests jobs in uniform random order, processes qualifying revealed jobs immediately, and finishes remaining jobs in shortest-processing-time order.Its leading coefficient is given by the stationary survival formula, and raw execution is the alternative q = 0 in the instance-optimal framework.Source: §5.1 · p. 74, Consequently the better of the raw and… · p. 74

Consequently the better of the raw and stationary algorithms has leading ratio

• The better of raw execution and the stationary threshold-prefix algorithm upper-bounds the instance-specific ratio, although interior mixtures can improve individual inputs.After maximizing over distributions, the endpoint choices q = 0 and q = 1 attain the sharp value; the lower bounds apply to all algorithms.Source: Consequently the better of the raw and… · p. 74

5.2 Flattening the survival function

• Flattening the survival function preserves the threshold constraint and stationary numerator while decreasing the offline denominator, reducing the optimization to binary distributions supported on {0, τD} or {0, u}.The {0, u} family governs the curve from u = 1 through u = 25/4, while the other family takes over at u = 25/4 and yields the 4/3 plateau.Source: §5.2 · pp. 75–76, Figure 5 · p. 75

5.3 The two scalar maximizations

• The first scalar family is maximized at τ = min{2, u −1} and equals 4/3 for u ≥ 3; the second increases until its optimizer and then decreases.Comparing both families establishes the announced upper bound for every finite distribution, with continuity at the transition points and a global interior maximum.Source: §5.3 · pp. 76–77

5.4 Worst-case upper bound from instance optimality

• The universal unannounced algorithm gives RO(u) · OPT_u + o_u(n^2), and for 0 < u ≤ 1 raw execution is also clairvoyantly optimal.This upper bound follows directly from the endpoint comparison, scalar bound, and exact empirical identity.Source: §5.4 · p. 77

5.5 Binary oblivious lower bounds

• For u > 1, Lemma 5.3 gives every randomized nonanticipating algorithm a binary-input envelope using xn + O(1) jobs of value u and (1−x)n + O(1) zero jobs.The construction applies even to announced algorithms, so adaptivity cannot improve the resulting worst-case upper bound.Source: §5.5 · p. 77
• The binary envelope has normalized lower-bound value (1 + x + ux^2)/2 when x ≤ (u−1)/u, up to o_u(1).The minimization occurs at tested fraction q = 1 after the completion-curve reduction.Source: §5.5 · pp. 77–78
• The lower-bound proof exposes job values only when labels are first touched, then replaces tests among the final o(n) untouched jobs by raw execution without changing total completion cost beyond o_u(n^2).A simultaneous predictable-permutation event controls every relevant prefix, avoiding conditioning on the algorithm’s adaptive stopping time.Source: §5.5 · p. 78
• The arguments apply to randomized algorithms by fixing the algorithm’s seed and averaging, while irrational binary masses are approximated by integer job counts with only O_u(n) rounding error.The private shuffle is part of the input convention, and the effective lengths are 1 and u.Source: §5.5 · pp. 78–79
• For u ≥ u_rand^3, Lemma 5.4 uses n/2 zero jobs and n/2 jobs of value two to obtain the 4/3 lower bound.For u > 3, the corresponding offline coefficient is 3/4 from equally weighted divisible SPT scheduling.Source: §5.5 · p. 79
• The binary lower bounds match the worst-case upper bound on 1 < u ≤ u_rand^3, while raw execution is optimal for 0 < u ≤ 1, completing Theorem 5.1.The matching lower bounds are supplied by the binary constructions and the balanced zero–two construction at the large-u endpoint.Source: §5.5 · p. 79

5.6.4 Analysis on good and bad samples

• The fixed-cutoff companion with B = 32 and fallback criterion bκ < 2/B achieves E ALG ≤ 4/3 · OPT + 20378n^7/4.The explicit estimate uses the same sampling analysis with a deliberately loose constant covering smaller n.Source: §5.6 · p. 80, §5.6.4 · p. 86

5.6.5 Transfer of the zero–two lower bound

• For arbitrarily large even n, an input with n/2 zero jobs and n/2 jobs of value two forces every randomized obligatory algorithm’s ratio to tend to 4/3.The revealing and obligatory transcripts coincide at the relevant cap, while expected online cost is n^2 − o(n^2).Source: §5.6 · p. 80, §5.6.5 · p. 86

5.6 The randomized obligatory endpoint

• 4/3 is the exact randomized size-asymptotic competitive ratio against an oblivious adversary, achieved by A∗ and matched by a zero–two lower bound.The theorem also gives a universal additive-error guarantee, while the fixed-cutoff companion satisfies E ALG ≤ 4/3 · OPT + 20378n^7/4.Source: §5.6 · p. 80, §5.6.5 · p. 86

5.6.2 Stationary prefixes

• The offline core is a maximum-density prefix of shortest jobs, and uniformly random testing yields an exact identity whose nonnegative terms establish the factor 4/3.A maximum-density prefix can be chosen using threshold τ, with prefix values at most τ and outside values at least τ.Source: §5.6 · p. 80, §5.6.2 · pp. 81–82

5.6.3 Learning the prefix from a sublinear sample

• The algorithm discretizes positive values, samples k jobs, learns a threshold-closed category prefix, and excludes the overflow category from the learned prefix.If the sample has no finite-category mass, it uses fallback; otherwise it processes learned-prefix jobs early and handles the rest by testing followed by SPT processing.Source: §5.6.3 · pp. 83–84

5.6.4 Analysis on good and bad samples

• On good samples, the learned schedule inherits the robust stationary-prefix bound, while fallback is bounded by 4/3 · OPT; bad samples contribute only controlled excess.With d = floor(n^1/4), k ≤ n^3/4, and B_n = O(n^1/20), the resulting error terms are lower order and yield the uniform theorem bound.Source: §5.6.4 · pp. 84–85

6 Blind optimization: speedup without revelation

• The blind-optimization model hides pi until an optimized job finishes, eliminating the threshold decision and making the revealing model’s bounded randomized ratio depend on revealed information.Raw execution takes u time, while optimization takes one unit and produces a hidden duration pi ∈[0, u].Source: §6 · p. 86

6.2 Proof of randomized instance optimality

• The randomized instance-specific benchmark is determined by the smaller of raw completion cost u and average optimized completion cost 1 + µp, while no announced randomized algorithm can asymptotically beat it.The lower bound is 2 min{u, 1 + µp} − o_u(1) at the leading normalized scale.Source: §6 · p. 87, §6.2 · pp. 92–93
• Randomization is necessary for instance-optimality, but one universal algorithm attains the benchmark for every input using only the empirical mean µp.It samples k = ⌈n^2/3⌉ jobs, estimates µp, and chooses optimization when 1 + µp is below u; otherwise it runs the remainder raw.Source: §6 · p. 87, §6.1 · p. 91, §6.2 · p. 93

6.1 The deterministic worst-case curve

• The exact deterministic worst-case policy runs every job raw for u ≤ 2 and optimizes every job for u ≥ 2, with the two policies meeting at u = 2.The matching lower and upper bounds are tight on binary inputs with values zero and u, with optimized jobs ordered first in the worst case.Source: §6.1 · pp. 89, 91

6.3 The exact worst-case curve

• The exact worst-case analysis identifies the blind-optimization threshold u_BO as the unique root greater than one of u^3 − 2u^2 − u + 1 = 0, namely 1 + 2 cos(2π/7) = 2.24 . . . .The clairvoyant scheduler orders effective lengths min{u, 1 + pi} shortest first when forming the instance-specific ratio.Source: §6.3 · p. 93
• Theorem 6.6 gives the exact optimal randomized size-asymptotic competitive ratio for BO(u) against an oblivious adversary.The proof combines a universal upper algorithm with shuffled binary inputs establishing matching lower bounds.Source: §6.3 · pp. 94–95
• A binary distribution with optimized length 0 and raw length u attains equality in the upper-bound inequalities, establishing the worst-case curve.Its survival function is constant on [0, u), making both inequalities tight.Source: §6.3 · p. 94
• The optimizer switches at uBO, where b∗(u) meets b0; b0 is optimal before the threshold and b∗(u) afterward.The threshold is characterized by u3 −2u2 −u + 1 = 0.Source: §6.3 · p. 95
• The hard instances place most jobs at optimized length 0 and a small fraction at length u, which blind optimization cannot recognize before committing.The clairvoyant schedule optimizes the zeros, runs length-u jobs raw, and places them last; revelation permits deferring those jobs after testing.Source: §6.3 · p. 95