PaperlayerView exact revision on arXiv

Source-linked AI summary

Test or Run? Scheduling Jobs of Unknown Length

Václav Rozhoň

arXiv:2608.30911v1cs.DS

TL;DR

The paper asks how to schedule jobs when testing reveals their lengths but consumes time, across several information-and-speedup variants. It develops threshold, sampling, and potential-based analyses to obtain exact competitive curves and instance-optimal algorithms. The main scope boundary is that the strongest instance-optimal and finite-guarantee results require bounded job lengths, with randomization where stated.

  • Problem

    The problem is to minimize total completion time when job lengths are hidden and inspecting a job costs one unit of machine time.

  • Method

    The paper analyzes obligatory testing, revealing optimization, and blind optimization using threshold algorithms, random sampling, and potential-based proofs.

  • Results

    The paper proves exact deterministic and randomized competitive ratios for the studied variants, including 1.57... and 4/3 for obligatory testing and six-piece and four-piece revealing-optimization curves.

  • Takeaways & Limitations

    Simple randomized algorithms can be instance-optimal on every input with lengths bounded by a fixed finite limit in the relevant models.

  • Takeaways & Limitations

    Without an upper bound on job lengths, no randomized blind-execution algorithm has a finite competitive ratio, and the instance-optimality assumptions require a fixed bound and randomization.

Abstract

from arXiv · show

A machine faces many jobs whose lengths are hidden. Spending one unit of time to inspect a job may reveal a short job that should be finished now, or it may reveal nothing useful while every other job waits. When should the machine keep looking, and when should it start working? We study natural variants of this question and provide optimal algorithms in both the worst-case and instance-optimal frameworks. The resulting algorithms are often quite simple, which may make them useful in practice.

1 Introduction

The paper studies scheduling when job lengths are hidden and testing costs time, covering obligatory testing, revealing optimization, and blind optimization. It derives exact worst-case ratios and randomized instance-optimal algorithms, with guarantees that depend on boundedness and the model variant.

  • 1 Introduction: Testing trades information about short jobs against delaying every unfinished job, so the scheduler must balance learning with execution.Opening a paper costs one unit, which can add substantially to total completion time when many jobs remain.
  • 1.1 Warmup: every job has to be tested: 1.57... deterministic and 4/3 randomized asymptotic competitive ratios are optimal in the obligatory-testing model.The randomized lower bound uses inputs containing equal numbers of zero-length and two-length jobs with shuffled labels.
  • 1.2 One algorithm for every bounded input multiset: A single randomized algorithm is instance-optimal on every fixed bounded input class, even against online algorithms given the input multiset in advance.The result requires a finite upper bound L and randomization; the algorithm itself is a simple threshold algorithm.
  • 1.5 Blind optimization: For blind optimization, the worst-case ratio grows as Θ(√u), while randomization improves the asymptotic ratio by a factor of two.Hard instances contain roughly a 1/√u fraction of jobs that cannot be shortened and the rest optimized to zero length.
  • 1.6 Revealing optimization: In revealing optimization, the exact deterministic and randomized curves are six-piece and four-piece curves, respectively, with maxima 1.86... and 1.62... .The deterministic curve eventually falls to 1.57..., while the randomized curve eventually becomes 4/3.
  • 1 Introduction: The paper supplies algorithms and matching analyses for revealing optimization, obligatory testing, and blind execution, including randomized instance-optimality results.The exact curves are nonmonotone, and the paper relates their bounded behavior to the value of advance information.

2 Models and common preliminaries

The paper formalizes four scheduling models that differ in whether a unit preliminary action reveals a hidden processing time, speeds execution, or both. It defines the adversarial, randomized, offline, and instance-optimal comparison frameworks used throughout.

  • Model definitions: Four models differ in what operations are available before a job’s hidden processing value becomes known.The common setting has n jobs, one nonpreemptive machine, and hidden nonnegative values p_j.
  • Model definitions: In obligatory testing, every job is tested for one unit, revealing p_j before its processing operation is scheduled.Testing cannot be skipped in this model.
  • Model definitions: Blind execution permits either blind processing for p_j or one-unit testing, but testing reveals information without shortening the job.The value becomes known only after blind execution finishes or immediately after testing.
  • Model definitions: Blind optimization replaces raw execution time u with p_j after a unit optimization action, without revealing p_j before execution.Raw execution takes known time u and reveals no hidden value.
  • Model definitions: Revealing optimization combines the unit speedup and information benefits by revealing p_j before the subsequent processing operation.The alternative to raw execution is a unit test followed by processing for p_j.
  • Benchmarks and comparisons: The offline benchmark orders jobs by effective length, using 1 + p_j in obligatory testing, p_j in blind execution, and min{u, 1 + p_j} in optimization models.The clairvoyant optimum chooses the shorter available completion mode and keeps each resulting block contiguous.

3 The fluid model and instance optimality

The instance-optimality analysis replaces shuffled finite job populations with a fluid problem whose exact value captures the leading n^2 completion-cost term. This common model supports results for revealing optimization, obligatory testing, and blind execution.

  • Instance-optimality framework: The paper proves instance-optimality results for revealing optimization, obligatory testing, and blind execution using one common fluid model.It first solves the fluid problem exactly and then transfers its value to every bounded input.
  • Instance-optimality framework: Private shuffling makes the observed prefix composition approximate the full input distribution, so testing a fraction t exposes approximately fraction t of every processing-time class.The algorithm’s inspection decisions may depend on observed jobs but not on still-hidden values.
  • Instance-optimality framework: The fluid model makes this sampling approximation exact by replacing n jobs with divisible unit mass and scaling machine work by n.Testing mass 0.01 reveals exactly a 0.01 copy of the input distribution, describing the leading n^2 term.

3.1 The fluid model

The fluid model represents schedules as finitely many divisible testing and processing blocks, ordered by completion density. Its completion curve converts total completion cost into the area of unfinished mass, enabling exact block-level optimization.

  • Fluid schedules: A fluid schedule consists of divisible blocks that test mass, process selected outcomes immediately, or process deferred jobs by type.Testing blocks use selectors to choose which revealed positive types are completed directly; deferred queues retain the rest.
  • Completion curves: The completion curve C(x) records completed mass after x units of work and is piecewise linear for every finite fluid schedule.Positive-work blocks are traversed linearly, while zero-work blocks complete their mass immediately.
  • Completion curves: Total completion cost equals the area under unfinished mass, represented geometrically by the area between completed mass and total mass.The layer-cake identity equates the integral of unfinished mass with the area under the completion curve; Figure 3 illustrates this shaded region.
  • Testing-block optimization: The maximum-density testing block selects every positive type below threshold τ_D and may fractionally select the type equal to τ_D.The threshold satisfies τ_D ≥ 1, and the resulting block has maximum completion density 1/τ_D.
  • Testing-block optimization: The threshold selector attains equality in the density bound, yielding w* = τ_Da* and maximum density 1/τ_D.Deferred positive types have support at or above τ_D and therefore require at least as much work per completion as the testing block.
  • Fluid schedules: Each block is characterized by completed mass and work per completion, and blocks are ordered by increasing work per completion.This is the divisible analogue of shortest-processing-time order.

3.2 The optimal fluid schedule

For fixed distribution D, tested fraction q, and alternative cost v, FluidSPT constructs a maximum-density testing block followed by shortest-work-per-completion blocks. Its completion curve dominates every feasible fluid schedule pointwise, yielding optimal total completion time.

  • State and envelope: The fluid model tracks tested mass, alternative-completed mass, and processed positive mass by type under explicit feasibility constraints.These aggregate variables form a finite-dimensional envelope containing every feasible schedule.
  • Block construction: A maximum-density selector determines one testing block with completion mass qa∗ and work per completion τD.The selector is computed from the distribution and then used to construct the testing block.
  • Block construction: The remaining mass is represented by deferred positive-type blocks and an alternative-completion block of mass 1 −q and work per completion v.Deferred type-i blocks have work per completion pi, while the alternative block has work per completion v.
  • Shortest-first execution: All nonempty blocks are ordered by nondecreasing work per completion, with testing preceding deferred blocks on ties.This is the FluidSPT schedule used to realize the optimal completion curve.
  • Optimality: FluidSPT(D, q, v) attains the envelope equality for every work budget and therefore minimizes fluid total completion time.The proof combines the universal envelope upper bound with a schedule that realizes it simultaneously at every x.
  • Finite implementation: The finite-input transfer learns the empirical distribution from a sublinear private sample and runs the corresponding fluid algorithm in finite batches.The same framework specializes to revealing optimization and blind execution through different direct-mode costs.

3.3 From fluid schedules to finite inputs

The paper transfers the fluid optimum to finite inputs by learning a rounded empirical distribution from a random subsample and implementing its block plan. Concentration, rounding stability, and plan stability provide matching upper and lower bounds up to vanishing normalized error.

  • Common model: The common finite model lets a job be tested for one unit or completed directly for r(p), with the first-touch choice made before p is known.The parameter set Q determines whether both modes or only testing are available.
  • Specializations: The three applications use r(p)=u for revealing optimization, r(p)=p for blind execution, and Q={1} for obligatory testing.In blind execution, the direct-mode cost is based on the distribution’s mean; blind optimization is outside this common model.
  • Approximation guarantees: The finite-to-fluid theorem combines the learned-plan upper bound with a lower bound that remains valid even when the competing algorithm is told the input multiset.Both bounds use vanishing errors and include the algorithms’ private randomness.
  • Learning: A random subsample learns a rounded empirical distribution, while predictable-permutation concentration controls cell frequencies and direct-mode work across prefixes.The construction preserves zero as a separate class and rounds positive values to a finite grid.
  • Finite implementation: The finite schedule handles the final δn n+O(1) untouched jobs by assigning them one legal mode, changing only a sublinear suffix.This suffix edit contributes only a vanishing normalized error.
  • Finite implementation: Fixed grid plans can be implemented by uniformly selecting test labels, with guarantees uniform over grid distributions, frequencies, and plans.The implementation uses a private uniform permutation and makes the tested-fraction decision before values are exposed.
  • Approximation guarantees: Plan stability and rounding stability bound changes in fluid cost, allowing the learned rounded plan to approximate the original empirical optimum.The coupling argument gives a horizontal 2h completion-curve shift and area difference at most 2h.

3.4 Revealing-optimization instance optimality

For revealing optimization, untested jobs run for the public raw time u, while tested jobs use the optimal fluid block structure. The optimal tested fraction is obtained by explicitly minimizing a convex quadratic, and the finite algorithm is instance-optimal for every fixed u.

  • Model and schedule: Revealing optimization uses direct-mode cost r(p)=u, so an untested job runs for u independently of its hidden processing time.The common fluid model therefore has v=u and permits any tested fraction q∈[0,1].
  • Instance optimality: For every fixed u>0, randomized nonanticipating algorithms achieve and cannot improve on the instance-specific optimum up to a vanishing asymptotic error.The lower bound remains valid even against an announced randomized competitor.
  • Model and schedule: When τD<u, shortest-first order runs the testing block, residual types in SPT order, and finally the raw block.The resulting cost separates testing, residual delay, residual SPT cost, and raw execution contributions.
  • Model and schedule: When τD≥u, pure raw execution pointwise dominates every positive tested fraction.In this regime, every testing or residual block has work per completion at least u.
  • Optimizing the tested fraction: The completion envelope is concave in q, making unfinished-mass area convex and reducing the optimization to an explicit quadratic minimization.The quadratic coefficient satisfies B≥0.
  • Optimizing the tested fraction: q∗=1 when B=0, and q∗=min{1, −A/(2B)} when B>0.This formula gives the minimizing tested fraction for the revealing-optimization fluid problem.

3.5 Obligatory-testing instance optimality

In obligatory testing, every job is tested, so the optimal schedule uses a maximum-density testing block followed by a deferred SPT tail. A single randomized algorithm learns this structure on every fixed bounded input class, while deterministic or unbounded-input instance optimality is impossible.

  • Optimal fluid schedule: Obligatory testing fixes q=1, leaving only the maximum-density testing block and its deferred SPT tail.The paper also gives a single algorithm that does not require knowing the processing-time bound in advance.
  • Instance-optimal algorithm: A single randomized nonanticipating algorithm is asymptotically instance-optimal for every fixed L and every input in [0,L]n.Its normalized error can be taken as O_L(n^-1/5), uniformly over each bounded input class.
  • Optimal fluid schedule: The fluid optimum equals the testing-block area plus the internal SPT area of the residual block.This decomposition is attained up to O(Ln) when the input multiset is announced.
  • Instance-optimal algorithm: The algorithm privately samples k=⌊n^3/4⌋ jobs, uses a growing cutoff Bn and grid mesh η, then selects a maximum-density category prefix.Overflow values are never selected, and absent finite categories are included through the closure rule.
  • Instance-optimal algorithm: The learned plan processes selected positive jobs and finishes remaining positive jobs in SPT order, with sample and learning errors controlled by concentration and stability bounds.The proof combines the growing-cutoff learning bound with the obligatory-testing lower bound.
  • Impossibility boundaries: Randomization and bounded inputs are necessary: no deterministic algorithm is instance-optimal even on [0,2], and no randomized algorithm has the same guarantee over unbounded lengths.The deterministic lower bound uses a fixed labeling with half zero and half length-two jobs.
  • Impossibility boundaries: On the hard bounded instance, the comparison randomized algorithm costs n^2+3n/4.The construction tests in random order, completes zeros immediately, defers length-two jobs, and processes them last.

3.6 Blind-execution instance optimality

The blind-execution model admits an instance-optimal randomized algorithm for every bounded job-length range, but no finite worst-case ratio exists without such a bound. The optimal fluid policy combines testing, selective processing, blind execution, and a final tail according to density.

  • Fluid structure: The optimal fluid algorithm uses a maximum-density testing block, tested medium jobs, blindly executed jobs, and tested long jobs.The blocks are ordered by work per completion, with tested jobs satisfying τD < p < µ before blind execution and longer tested jobs afterward.
  • Instance optimality: For every fixed L < ∞, randomized algorithms achieve instance optimality on inputs p ∈[0, L]^n, with vanishing asymptotic error.The matching lower bound holds even when the algorithm is told the multiset of job lengths.
  • Fluid structure: The optimal tested fraction q minimizes an explicit quadratic cost determined by the job-length distribution.When τD ≥ µ, pure blind execution is optimal; otherwise the minimizing fraction is determined from the quadratic coefficients.
  • Example: For a distribution with µ = 57/5 and τD = 5, the optimal tested fraction is q∗=4/5 and the fluid value is 1249/250.Deferring all tested nonzero jobs until after blind execution gives 126/25, so that simpler ordering is not instance optimal.
  • Unbounded processing times: A fixed upper bound L is necessary: without it, blind execution has no finite worst-case ratio, even for randomized algorithms.A single exceptional job of length H = n^2 contradicts any finite-ratio guarantee when the algorithm is run on an all-zero history.

4 Deterministic revealing optimization and its obligatory endpoint

The paper derives the exact deterministic competitive curve for revealing optimization at every finite common upper limit u and proves the obligatory-testing ratio at its endpoint. Six formula intervals are matched by explicit algorithms and adversarial lower bounds.

  • Exact revealing-optimization curve: For every fixed 0 < u < ∞, the optimal deterministic size-asymptotic ratio in revealing optimization is given exactly by a six-interval formula.The intervals are separated by five transition points, including values 3.14... and 3.61....
  • Upper and lower matching: On every interval, the corresponding algorithm satisfies ALG ≤ RO(u) · OPT(I) + O_u(n).The additive remainder is one absolute O(n) term, uniform over finite u.
  • Obligatory endpoint: At the obligatory-testing endpoint, the deterministic size-asymptotic competitive ratio is exactly Rdet_OT = 1.57....The theorem supplies both adversarial lower bounds and an algorithmic upper bound with an O(n) additive term.
  • Lower bounds: The lower bounds use hidden binary stopping instances for smaller u and continuous or scaled harmonic constructions for larger u.At the high-u plateau, lower-bound instances can keep every p_j below u−1, making the offline cap inactive.
  • Algorithms: Three explicit algorithms match the deterministic curve: raw execution, forced-prefix uniform threshold, and history-dependent adaptive threshold.Each algorithm applies on consecutive ranges of u, with matching lower-bound constructions.

4.1 Upper bounds

The upper-bound analysis gives simple algorithms that attain the deterministic revealing-optimization curve across successive ranges of u. Their guarantees follow from raw execution, forced-prefix thresholding, and adaptive potential-based control.

  • Raw execution: Raw execution is optimal for u ≤ 1 and achieves the matching factor u through the first nontrivial transition point.For u ≤ 1, every offline effective length equals u; for larger u, the ratio is bounded by u in the stated range.
  • Forced-prefix uniform threshold: ForcedPrefixUTE tests every job, processes a forced prefix immediately, and thereafter uses a uniform threshold to defer longer outcomes.Deferred jobs are later processed in nondecreasing revealed processing time.
  • Forced-prefix uniform threshold: The forced-prefix algorithm satisfies ALG ≤ Rquad(u) · OPT + O_u(n) across its designated intermediate ranges.The guarantee is established separately below and above u = 2 and combined over the interval.
  • Analysis of forced-prefix UTE: Worst binary inputs place as many long jobs as possible in the forced prefix, then remaining long jobs at the suffix start, with zeros last.This ordering maximizes the completion cost for a fixed number of long jobs in the prefix.
  • Adaptive threshold: For larger u, AdaptiveThreshold satisfies (1 + c) · OPT + O_u(n) on the middle and high revealing ranges.Since offline effective lengths are at least one there, the additive terms vanish in the size-asymptotic ratios.
  • Adaptive threshold: The adaptive proof uses a nonnegative base potential and a reserve potential for jobs with p = u.The reserve term cancels the extra positive charge generated by endpoint jobs through its directional derivative.

4.2 Lower bounds

The lower-bound constructions establish the exact deterministic revealing-optimization curve by combining binary stopping games, harmonic instances, and a scaled hybrid at larger u. They also connect the high-u endpoint directly to obligatory testing without continuity arguments.

  • Binary lower bounds: Binary instances with p_j ∈{0, u} already yield the lower curve on the low- and intermediate-u ranges.The stopping point is hidden from the algorithm, and the reveal order can be converted into a fixed input.
  • Harmonic construction: For larger u, a scaled harmonic construction supplies lower bounds for obligatory-testing algorithms and revealing algorithms with short jobs.The harmonic core uses multilevel rational instances at growing scales.
  • Combined construction: At high u, neither the binary nor pure harmonic family is tight, so the adversary prepends p = u jobs to a scaled harmonic remainder.The later jobs satisfy 1 + p ≤ u, allowing the obligatory-testing lower bound to transfer.
  • Combined construction: The combined construction proves that every deterministic revealing algorithm has ratio at least 1 + c(u) for the high-u regime.Finite fixed instances can approach the limiting ratio arbitrarily closely.
  • Endpoint matching: The endpoint arguments are handled directly: the binary construction applies at u_det4, while the obligatory-testing harmonic bound applies at u_det5.No passage between models by continuity is used at either endpoint.

4.3 Assembly of the curve

The deterministic revealing-optimization curve is assembled from six formulas whose adjacent pieces join exactly and whose monotonicity determines its global maximum. Matching upper and lower bounds establish the complete fixed-u asymptotic curve, with stated additive remainders.

  • Curve shape: Rdet RO(u) attains its global maximum only at u = udet 5 after each relevant formula is shown strictly decreasing on its interval.The monotonicity lemma covers Rquad(u), 1 + 1/√u −1, and 1 + c(u).
  • Exact joins: The six deterministic formulas agree at all five transition points, producing a continuous piecewise curve.The joins are verified explicitly, including the final identity 1 + c(udet 5 ) = 1 + r = Rdet OT.
  • Matching bounds: Upper and matching lower bounds cover every interval of the deterministic curve, including the plateau for u ≥ udet 5.The proof pairs interval-specific lemmas and propositions, and the plateau uses instances where the offline cap is inactive.
  • Asymptotic guarantees: The finite upper bounds have additive error O_u(n), while the plateau has one absolute O(n) remainder.The theorem proof states the error behavior separately for finite intervals and the plateau.
  • Asymptotic scope: The section’s statements concern the fixed-u size-asymptotic competitive ratio.The asymptotic-scope remark limits the interpretation of the assembled curve to fixed u as n grows.

4.4 The obligatory endpoint

The obligatory model is obtained as the unbounded endpoint of revealing optimization through a uniform transfer, rather than formal substitution of u = ∞. The same algorithm and an error bound independent of u yield the endpoint guarantee, while plateau instances provide the lower bound.

  • Endpoint transfer: The obligatory model is the unbounded endpoint of revealing optimization, but reaching it requires uniformity in both the algorithm and additive error.The transfer relies on properties established for the finite curve rather than direct substitution.
  • Upper bound: AdaptiveThreshold with c = r is independent of u and never runs a job raw, so its revealing execution matches the obligatory execution on finite instances.Choosing u above every finite job value makes effective lengths coincide in the two models.
  • Upper bound: The constant B is independent of u, giving ALG ≤ Rdet OT · OPT + Bn for the obligatory model.The same inequality transfers from revealing optimization because the revealing and obligatory optima coincide on the selected instances.
  • Lower bound: The revealing plateau lower bound transfers by viewing any obligatory algorithm as a revealing algorithm at u = udet 5 that never uses raw execution.The witnessing instances satisfy pj < udet 5, leaving the offline cap inactive and preserving the online transcript.

5 Randomized revealing optimization: the exact four-piece curve

The randomized revealing-optimization problem is reduced to maximizing an instance-specific ratio over empirical distributions, yielding an exact four-piece curve. Survival-function flattening and binary lower bounds show that two simple candidate families suffice and match the upper bound.

  • Exact curve: Theorem 5.1 gives the optimal randomized size-asymptotic competitive ratio against an oblivious adversary for every fixed u > 0.The full exact curve is represented by four pieces and shown in Figure 4.
  • Reduction: Comparing the instance-optimal online cost with clairvoyant SPT and maximizing over distributions reduces the problem to two-value distributions and two scalar maximizations.A sublinear sample removes advance knowledge, while shuffled binary inputs provide matching lower bounds.
  • Stationary algorithm: The stationary algorithm tests jobs in random order, immediately processes positive jobs in a threshold prefix, and finishes deferred jobs in SPT order.Its thresholded behavior is summarized by the stationary pair identity specialized to the cap u.
  • Instance optimization: Choosing between raw execution and the stationary threshold algorithm gives an upper bound on every instance-specific ratio, although interior choices can improve individual inputs.The two endpoint choices are nevertheless sharp after maximizing over all distributions.
  • Distributional reduction: Flattening the initial survival function preserves the threshold constraint and stationary numerator while decreasing the offline coefficient, so it cannot lower the ratio.This reduces the distributional optimization to flat survival functions, illustrated in Figure 5.
  • Candidate families: The Bu family on {0, u} governs the curve through u = 25/4, while the A family on {0, τD} takes over thereafter and reaches the obligatory 4/3 plateau at τD = 2.The two families attain the reduced optimization’s candidate values.
  • Curve shape: The candidate formulas join continuously at their transition points, and the A family equals 4/3 for u ≥ 3.The transition and maximum statements follow from the candidate comparisons and derivative analysis.

5.4 Worst-case upper bound from instance optimality

Instance optimality converts the randomized algorithm’s per-input guarantee into the worst-case curve by bounding all algorithms on shuffled binary inputs. The resulting upper and lower bounds match across regimes, with raw execution optimal for u ≤ 1.

  • Upper bound: Applying the universal unannounced algorithm to the empirical distribution yields the instance-optimal upper bound on the worst-case ratio.The exact empirical identity contributes only a nonnegative linear correction and an o_u(n^2) remainder.
  • Low-cap regime: For 0 < u ≤ 1, raw execution is optimal for both the online algorithm and the clairvoyant scheduler, so learning is unnecessary.This regime completes the low-cap portion of the exact curve.
  • Binary envelope: Shuffled binary inputs provide an envelope that bounds completed mass for every deterministic algorithm and, after seed averaging, every randomized algorithm.The argument compares testing, known processing, and raw execution blocks by work per completion.
  • Error control: The binary-input analysis incurs only o_u(n^2) error after suffix editing, sampling failure, rounding, and omitted one-job terms are accounted for.The predictable-permutation event controls adaptive schedules while changing only a vanishing suffix.
  • Lower bounds: For the eventual 4/3 regime, balanced inputs with n/2 zero jobs and n/2 jobs of value two give a lower bound for every randomized algorithm.The effective lengths are one and three, and their equally weighted clairvoyant SPT cost supplies the offline coefficient.
  • Matching regimes: The binary lower bounds match the instance-optimal upper bound on 1 < u ≤ urand 3, while the bounded zero–two construction handles u ≥ urand 3.Together with the u ≤ 1 case, these results complete the exact randomized curve.

5.6 The randomized obligatory endpoint

The randomized obligatory-testing algorithm learns a near-optimal processing-time prefix from a sublinear sample, while a safe fallback handles values missed by sampling. It achieves the exact asymptotic ratio 4/3 against oblivious adversaries and is instance-optimal on every bounded class.

  • Guarantees: 4/3 is the exact randomized asymptotic competitive ratio against an oblivious adversary.The matching lower bound uses inputs with half zero jobs and half jobs of value two; the selected labeling has online cost n2 − o(n2).
  • Algorithm: The algorithm samples a sublinear set of jobs, estimates length categories, and selects a maximum-density prefix using a threshold.It rounds sampled values into bins, includes categories through the threshold, and protects against overflow values with a fallback schedule.
  • Scope: The robust analysis retains a linear correction so the guarantees remain valid for unbounded processing times, although instance-optimality requires a fixed bound L.Without a fixed bound, no randomized algorithm has a finite competitive ratio; for every fixed L, sampling yields one algorithm optimal on every bounded input.
  • Structural insight: The maximum-density prefix consists of the shortest jobs and maximizes completions per unit of testing and processing work.The exact identity for separated prefixes is identified as the algebraic source of the constant 4/3.

6 Blind optimization: speedup without revelation

Blind optimization separates speedup from revelation: optimization can shorten processing without revealing a job’s length, so the scheduler cannot defer unexpectedly long jobs. The paper proves exact deterministic and randomized worst-case curves, rules out deterministic instance-optimality, and gives a randomized algorithm optimal for every input.

  • Model: In the blind-optimization model, optimization reduces processing to pi ∈ [0,u] but reveals pi only when the job finishes.Raw execution takes the known time u, while optimized jobs must be started without knowing their duration.
  • Deterministic worst case: The optimal deterministic policy runs every job raw up to u = 2 and optimizes every job after that point.Its exact worst-case curve is tight for binary inputs containing zeros and a fraction of jobs with value u.
  • Instance optimality: No deterministic algorithm is asymptotically instance-optimal in BO(2), because an adversary can construct a fixed binary input matching the algorithm’s transcript.The comparison algorithm privately permutes jobs and chooses between optimizing individually or running every job raw.
  • Randomized instance optimality: A randomized algorithm is asymptotically optimal at the n2 scale for every input and needs only the empirical mean rather than a histogram or threshold.Choosing the wrong mode costs at most O(n2)|bµ − µp|, while the correct mode has leading cost n2ΦBO,u(p).
  • Worst-case separation: For large u, hard inputs place roughly a 1/√u fraction of jobs at length u and the rest at optimized length zero, yielding online cost Θ(n2√u) versus clairvoyant cost Θ(n2).The resulting separation reflects the scheduling value of revealed information: the optimum can place long jobs last, but blind optimization cannot identify them beforehand.
Loading 2608.30911v1…