Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Hardness of Obligatory-Test Scheduling on Multiple Machines

T0 review · 2 major / 5 minor · reviewed 2026-07-15 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A completion-threshold method shows that obligatory-test scheduling on identical machines cannot beat a competitive ratio of 3/2.

desk verdict Clean lower-bound framework that lifts the single-machine obligatory-test barrier from √2 to 3/2 and gives the first multi-machine hardness of the same strength. read the letter →

arxiv 2606.02029 v2 pith:UVR5Q6AZ submitted 2026-06-01 cs.DS

Kao-Chuan Liang , Ya-Chun Liang This is my paper · ORCID
classification cs.DS MSC 68W2768Q2590B35
keywords competitiveratiolowerboundsonlinealgorithmsschedulingwithtestingsumofcompletiontimesmultiplemachinesobligatory
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

When every job must be tested before its true processing length appears, an online scheduler on several identical machines must constantly choose whether to spend capacity on revealing unknown jobs or on finishing already-revealed ones. Earlier single-machine arguments only reached a lower bound of the square root of 2 and could not be copied to the parallel setting, because machines may interleave jobs freely and a job’s test need not finish on the same machine as its processing. This paper replaces those constructions with completion thresholds: the earliest times at which the first 1, 2, …, N jobs finish. Their sum equals the total completion-time objective, so any pointwise delay on those thresholds immediately yields a global lower bound. Using the method the authors obtain a three-type bound of 1.4811 and a dyadic multi-type family that approaches 3/2; the same family also lifts the single-machine lower bound from √2 to 3/2. They complement the hardness results with a simple priority list-scheduling rule that is 2-competitive for arbitrary test lengths.

What carries the argument

The completion-threshold identity ALG = ∑_X T_X, where T_X is the earliest time at which at least X jobs have finished; pointwise lower envelopes on the T_X’s under adversarial revelation order convert directly into lower bounds on total completion time.

What would settle it

Exhibit a deterministic online algorithm whose asymptotic ratio on the K-type dyadic family is strictly less than 3(2−4^{-K})/(4−4^{-K}) for large K, or prove that the offline optimum of that family is larger than the recursive balanced schedule used in the paper.

Watch

Extended reading notes

Core claim

The authors prove that no deterministic online algorithm for obligatory-test scheduling on m identical machines can achieve an asymptotic competitive ratio better than 3/2. The same construction simultaneously improves the best known deterministic single-machine lower bound from √2 to 3/2, while a matching algorithmic upper bound of 2 is given for arbitrary test times.

Load-bearing premise

The adversary is allowed to decide each job’s processing length solely by the order in which its test finishes; any algorithm that could force simultaneous test completions or otherwise break that total order would invalidate the pointwise envelopes on the thresholds.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies online scheduling with obligatory testing on m identical machines to minimize sum of completion times. Every job has a known test length and an unknown processing length revealed only after the test finishes; the algorithm must allocate capacity between testing and processing. The authors introduce completion thresholds TX (earliest time at which at least X jobs finish) and the identity ALG = sum TX. Using this, they prove a three-type lower bound of 1.4811 (Theorem 2) and a K-type dyadic construction whose ratio tends to 3/2 (Theorem 5); the same construction improves the single-machine deterministic lower bound from √2 to 3/2 (Corollary 14). They also give a simple priority list-scheduling algorithm A1 that is 2-competitive for arbitrary test times (Theorem 16) and show that other parameters in the same priority family cannot improve the asymptotic ratio.

Significance. The work supplies the first nontrivial deterministic lower bounds for the multi-machine obligatory-test model and simultaneously strengthens the single-machine lower bound. The completion-threshold framework cleanly handles the obstacles that prevent simple replication of single-machine adversaries (interleaving across machines, test and processing on different machines). The 3/2 barrier is a clean, natural number that matches the best known single-machine upper bound of 1.585 up to a small gap, and the 2-competitive multi-machine algorithm is simple and works for non-uniform tests. These results close an evident gap left by the recent ESA 2024 paper and give a reusable analytic tool for related testing models.

major comments (2)
  1. Abstract vs. body inconsistency on the algorithmic result. The abstract claims a parallelization of single-machine 1-SORT whose ratio is 2(m+ρ-1)/(m+1) whenever the single-machine algorithm is ρ-competitive. Section 4 instead presents a self-contained priority rule Aγ and proves only the special case γ=1 yields ratio 2 (Theorem 16). Either the general reduction should be stated and proved, or the abstract should be corrected to match the body.
  2. Table 1 lists a multi-machine lower bound of 3/2 for both uniform and non-uniform tests, yet all constructions (Theorems 2 and 5) use unit tests. While the uniform lower bound immediately applies to the non-uniform model, the table entry should be annotated to avoid the impression that a non-uniform-specific construction is given.
minor comments (5)
  1. Lemma 1 proof: the notation Ar for the cumulative number of completions is standard but could be clarified by an explicit sentence that TX is constant on each block [Ar-1+1,Ar].
  2. Figure 1 caption: the statement that g4 follows f2 on [1/16,1/8] is correct, but the figure itself would be clearer if the active branch intervals were shaded or labeled.
  3. Section 4.1: the tie-breaking rule “in favor of testing” is used crucially in the case analysis of Lemma 24; a short remark that the opposite tie-break would invalidate some inequalities would help the reader.
  4. References: the ESA 2024 paper is cited as [5]; the arXiv version number or DOI should be added for permanence once available.
  5. Typographical: several places write “√2” without the surrounding math mode consistently (e.g., abstract vs. introduction).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: lower bounds arise from explicit adversarial constructions and capacity arguments; upper bound is a self-contained list-scheduling analysis.

full rationale

The paper’s central claims (three-type ratio 1.4811, dyadic multi-type limit 3/2, and the 2-competitive algorithm) are obtained by direct constructions and elementary work accounting. Processing times are assigned by an adaptive adversary that depends only on the order of completed tests (Definition 4, Theorem 2); the resulting pointwise lower envelopes on the completion thresholds TX (Lemmas 3 and 6) follow from total machine capacity mTX and the obligatory-test prerequisite. Summing/integrating those envelopes (Lemmas 1, 11–12) and comparing against an explicit offline schedule (Lemma 13) yields the stated ratios without any fitted parameters or self-referential normalizations. The single-machine improvement (Corollary 14) is simply the m=1 special case of the same construction. The algorithmic side (Theorem 16) bounds pairwise contributions under the priority rule A1 and compares them with a standard OPT lower bound; the argument never invokes a uniqueness theorem or an ansatz taken from prior work of the same authors. The only self-citation is the historical ESA 2024 √2 benchmark, which is superseded rather than used as a load-bearing premise. Consequently the derivation chain is self-contained and free of the circular patterns listed in the instructions.

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The paper is a pure competitive-analysis result. It rests on standard online-scheduling axioms (adversarial revelation, identical machines, non-preemptive operations) plus the obligatory-test model definition. No free parameters are fitted; the only numerical constants are the dyadic proportions chosen for analytic convenience and the golden-ratio identity used for the optional-test side remark.

assumptions (3)
  • domain assumption Processing times may be assigned by an adversary after observing the order of test completions (standard competitive-analysis adversary).
    Invoked throughout Section 3; without it the pointwise TX lower envelopes cannot be forced.
  • domain assumption Every job must complete its test before its processing operation may begin (obligatory-test model).
    Definition in Section 2; the entire TX framework relies on this mandatory revelation stage.
  • standard math Machines are identical and operations are non-preemptive; list scheduling assigns each selected operation to a least-loaded feasible machine.
    Standard multiprocessor scheduling model used for both lower and upper bounds.
invented entities (1)
  • completion threshold TX
    purpose: Converts global machine-capacity progress into an exact sum that equals total completion time, enabling multi-machine lower bounds.
    Defined in Section 2 (Lemma 1); the central analytic device of the paper. It is a derived quantity, not a physical postulate, so independent_evidence is false by construction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hardness of Obligatory-Test Scheduling on Multiple Machines." pith.science (2026). https://pith.science/paper/UVR5Q6AZ

@misc{pith2026260602029,
  author       = {Pith},
  title        = {Pith review of: Hardness of Obligatory-Test Scheduling on Multiple Machines},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UVR5Q6AZ}},
  note         = {Machine review of arXiv:2606.02029}
}
abstract

We study online scheduling with obligatory testing on $m$ identical parallel machines, with the objective of minimizing the sum of completion times. Each job comprises a test of known length and a processing operation of initially unknown length. The processing time is revealed only when the test completes. Unlike in optional testing models, the scheduler does not choose whether to acquire information. Instead, it must decide how to allocate machine capacity between testing unrevealed jobs and processing jobs whose sizes are already known. Previous single-machine lower-bound constructions suggest a natural $\sqrt{2}$ benchmark [ESA 2024: 48:1-14]. However, these constructions cannot be directly transferred to identical parallel machines by a simple replication argument. An online algorithm may interleave jobs from different copies, and the test and processing operation of a job need not be scheduled on the same machine. We address this difficulty by introducing a completion-threshold framework that reasons directly about global progress under total machine capacity. For each $X$, let $T_X$ be the earliest time at which the algorithm has completed at least $X$ jobs. The identity $\sum_{X=1}^{N}T_X$ then converts pointwise progress bounds into lower bounds on the total completion time. Using this framework, we prove a three-type lower bound of $1.4811$ and a dyadic multi-type lower bound tending to $3/2$. The latter also improves the deterministic single-machine lower bound from $\sqrt{2}$ to $3/2$. On the algorithmic side, we give a parallel version of single-machine 1-SORT and prove that, if single-machine 1-SORT is $\rho$-competitive, then its parallel version is $\frac{2(m+\rho-1)}{m+1}$-competitive on $m$ identical machines.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model

    cs.DS 2026-06 unverdicted novelty 7.0 of 10

    Presents deterministic (2.3166) and randomized (2.1523) constant-competitive algorithms for weighted single-machine scheduling with testing, extended via list scheduling to parallel machines (2.7763/2.5110).

Reference graph

Works this paper leans on

14 extracted references · cited by 1 Pith paper

  1. [1]

    Explorable uncertainty in scheduling with non-uniform testing times

    Susanne Albers and Alexander Eckl. Explorable uncertainty in scheduling with non-uniform testing times. In Approximation and Online Algorithms (WAOA 2020) , volume 12806 of Lecture Notes in Computer Science , pages 127--142. Springer, 2020. https://doi.org/10.1007/978-3-030-80879-2_9 doi:10.1007/978-3-030-80879-2_9

    doi:10.1007/978-3-030-80879-2_9 2020

  2. [2]

    Scheduling with testing on multiple identical parallel machines

    Susanne Albers and Alexander Eckl. Scheduling with testing on multiple identical parallel machines. In Algorithms and Data Structures: 17th International Symposium, (WADS 2021) , volume 12808 of Lecture Notes in Computer Science , pages 29--42. Springer, 2021. https://doi.org/10.1007/978-3-030-83508-8_3 doi:10.1007/978-3-030-83508-8_3

    doi:10.1007/978-3-030-83508-8_3 2021

  3. [3]

    Kononov, Giorgio Lucarelli, and Fanny Pascual

    Evripidis Bampis, Konstantinos Dogeas, Alexander V. Kononov, Giorgio Lucarelli, and Fanny Pascual. Speed scaling with explorable uncertainty. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2021) , pages 83--93. ACM, 2021. https://doi.org/10.1145/3409964.3461812 doi:10.1145/3409964.3461812

    doi:10.1145/3409964.3461812 2021

  4. [4]

    Felix Buld and Andreas S. Schulz. Scheduling with testing: Competitive algorithms for minimizing the total weighted completion time in the adversarial model. In Frontiers of Algorithmics (IJTCS-FAW 2025) , volume 15828 of Lecture Notes in Computer Science , pages 64--77. Springer, Singapore, 2025. https://doi.org/10.1007/978-981-96-8312-3_5 doi:10.1007/97...

    doi:10.1007/978-981-96-8312-3_5 2025

  5. [5]

    Scheduling with obligatory tests

    Konstantinos Dogeas, Thomas Erlebach, and Ya-Chun Liang. Scheduling with obligatory tests. In 32nd Annual European Symposium on Algorithms (ESA 2024) , volume 308 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 48:1--48:14. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.48 doi:10....

    doi:10.4230/lipics.esa.2024.48 2024

  6. [6]

    u rr, No \

    Fanny Dufoss \'e , Christoph D \"u rr, No \"e l Nadal, Denis Trystram, and \'O scar C. V \'a squez. Scheduling with a processing time oracle. Applied Mathematical Modelling , 104:701--720, 2022. https://doi.org/10.1016/j.apm.2021.12.020 doi:10.1016/j.apm.2021.12.020

    doi:10.1016/j.apm.2021.12.020 2022

  7. [7]

    Scheduling with explorable uncertainty

    Christoph D \"u rr, Thomas Erlebach, Nicole Megow, and Julie Mei ner. Scheduling with explorable uncertainty. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , pages 30:1--30:14, 2018. https://doi.org/10.4230/LIPIcs.ITCS.2018.30 doi:10.4230/LIPIcs.ITCS.2018.30

    doi:10.4230/lipics.itcs.2018.30 2018

  8. [8]

    An adversarial model for scheduling with testing

    Christoph D \"u rr, Thomas Erlebach, Nicole Megow, and Julie Mei ner. An adversarial model for scheduling with testing. Algorithmica , 82(12):3630--3675, 2020. https://doi.org/10.1007/s00453-020-00742-2 doi:10.1007/s00453-020-00742-2

    doi:10.1007/s00453-020-00742-2 2020

Show all 14 references
  1. [9]

    Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time

    Mingyang Gong, Zhi-Zhong Chen, and Kuniteru Hayashi. Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica , 86:1400--1427, 2024. https://doi.org/10.1007/s00453-023-01198-w doi:10.1007/s00453-023-01198-w

    2024 doi

  2. [10]

    Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments

    Mingyang Gong, Jing Fan, Guohui Lin, Bing Su, Zihan Su, and Xiang Zhang. Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments. Journal of Scheduling , 28(5):513--527, 2025. https://doi.org/10.1007/s10951-025-00850-3 doi:10.1007/s10951-02...

    2025 doi

  3. [11]

    Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing

    Mingyang Gong, Randy Goebel, Guohui Lin, and Eiji Miyano. Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing. Journal of Combinatorial Optimization , 44(1):877--893, 2022. https://doi.org/10.1007/s10878-022-00865-y doi:10.1007/s10878-02...

    2022 doi

  4. [12]

    Improved approximation algorithms for multiprocessor scheduling with testing

    Mingyang Gong and Guohui Lin. Improved approximation algorithms for multiprocessor scheduling with testing. In Frontiers of Algorithmics / International Joint Conference on Theory and Applications of Models of Computation, IJTCS-FAW 2021 , volume 12874 of Lecture Notes in Comp...

    2021 doi

  5. [13]

    Magnanti, and Yaron Shaposhnik

    Retsef Levi, Thomas L. Magnanti, and Yaron Shaposhnik. Scheduling with testing. Management Science , 65(2):776--793, 2019. https://doi.org/10.1287/mnsc.2017.2973 doi:10.1287/mnsc.2017.2973

    2019 doi

  6. [14]

    Alison Hsiang-Hsuan Liu, Fu-Hong Liu, Prudence W. H. Wong, and Xiao-Ou Zhang. The power of amortization on scheduling with explorable uncertainty. In Approximation and Online Algorithms (WAOA 2023) , volume 14297 of Lecture Notes in Computer Science , pages 90--103. Springer, ...

    2023 doi

Pith tools

Reviewed July 15, 2026 · model on record in the stance chip above.