pith. sign in

arxiv: 2503.13357 · v2 · submitted 2025-03-17 · 💻 cs.DM

The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty

Bob Krekelberg , Alison Hsiang-Hsuan Liu , Fu-Hong Liu , Prudence W.H. Wong , Xiao-Ou Zhang This is my paper

Pith reviewed 2026-05-23 00:32 UTC · model grok-4.3

classification 💻 cs.DM
keywords online schedulingexplorable uncertaintycompetitive analysistotal completion timesingle machinemultiple machinesvariable testing timesrandomized algorithms
0
0 comments X

The pith

Algorithms achieve competitive ratios of 2.316513 and 2.152271 for single-machine scheduling under explorable uncertainty.

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

The paper examines online scheduling to minimize total completion time when each job has an upper bound on its processing time that testing can potentially reduce. It focuses on the variable testing times setting and allows testing and processing to occur on different machines in the multi-machine case. By enhancing prior analysis frameworks, the authors obtain tighter competitive ratio bounds for both deterministic and randomized algorithms. A sympathetic reader cares because these bounds give stronger worst-case performance guarantees for deciding which jobs to test and how to order them online.

Core claim

Using an enhanced analysis framework, there exists a deterministic single-machine algorithm with competitive ratio 2.316513, a randomized algorithm with expected ratio 2.152271, and for m machines deterministic and randomized ratios of 2.77629-(0.45977/m) and 2.51098-(0.3587/m) respectively.

What carries the argument

The enhanced analysis framework that refines competitive ratio proofs for algorithms deciding testing, ordering, and machine allocation under variable testing times.

If this is right

  • The deterministic single-machine algorithm is at most 2.316513-competitive.
  • The randomized single-machine algorithm has expected competitive ratio at most 2.152271.
  • The deterministic multi-machine algorithm is 2.77629-(0.45977/m)-competitive.
  • The randomized multi-machine algorithm is 2.51098-(0.3587/m)-competitive.
  • When m equals 1 the multi-machine ratios match the single-machine results.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same framework could be applied to other objectives such as minimizing makespan if the analysis steps carry over.
  • Implementations might prioritize testing jobs whose upper bounds suggest large potential reductions relative to testing cost.
  • For very large m the ratios approach constants near 2.78 and 2.51, indicating the approach scales without degradation.
  • Related online problems with testing options and uncertainty might admit similar ratio improvements through refined charging arguments.

Load-bearing premise

The variable testing times model holds and testing and processing of a job may occur on different machines.

What would settle it

An adversarial sequence of jobs where the algorithm's total completion time exceeds 2.316513 times the optimal offline total completion time on a single machine would disprove the deterministic claim.

Figures

Figures reproduced from arXiv: 2503.13357 by Alison Hsiang-Hsuan Liu, Bob Krekelberg, Fu-Hong Liu, Prudence W.H. Wong, Xiao-Ou Zhang.

Figure 1
Figure 1. Figure 1: An example where p ∗ k is charged four times. The light blue and dark blue segments represent c(k, j) and c(j, k), respectively. The red segment represents p ∗ k . 3 Deterministic algorithms In this section, we first enhance the framework by equipping it with amortized analysis in Subsection 3.1. Using amortized arguments, for any two jobs k ≤o j, we manage to charge the sum of c(k, j) + c(j, k) to p ∗ k .… view at source ↗
Figure 2
Figure 2. Figure 2: The red arrows illustrate how to charge c(k, j)+c(j, k) to the cost of tasks regarding k. Each row in the sub-figures is a permutation of how the tasks are executed. The circles and rectangles are testing tasks and execution tasks after testing, respectively. The rectangles with curly tops are execution tasks without testing. The tasks in gray are from the job k, and the tasks in white are from the job j. … view at source ↗
read the original abstract

We study online scheduling to minimize total completion time with explorable uncertainty on single and multiple machines. Each job comes with an upper limit of its processing time, which could be potentially reduced by testing the job, which also takes time. The objective is to schedule all jobs with minimum total completion time. The challenge lies in deciding which jobs to test, the order of testing/processing jobs, and in multiple machine case which machine a job is allocated to. In multiple machine case, testing and processing of a job are allowed to be scheduled on different machines. Different settings have been studied before. In this work, we first consider the variable testing times setting. We enhance the analysis framework in Albers and Eckl (2020) and improve the analysis of the competitive ratio of their deterministic single machine algorithm from $4$ to $1+\sqrt{2} \approx 2.4143$. Using the new analysis framework, we propose a new deterministic algorithm that further improves the competitive ratio to $2.316513$. The new framework also enables us to develop a randomized algorithm improving the expected competitive ratio from $3.3794$ to $2.152271$. We further show that with $m$~machines, by extending the framework of Gong et al. (2024), there exists a deterministic $2.77629-(0.45977/m)$-competitive algorithm and a randomized $2.51098-(0.3587/m)$-competitive algorithm. The performance of the algorithms on multiple machines when $m = 1$ matches the current best algorithms on a single machine for variable testing times shown in this paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript studies online scheduling to minimize total completion time under explorable uncertainty, where each job has an upper bound on its processing time that may be reduced by testing (which consumes time). It focuses on the variable testing times model, allowing testing and processing on different machines in the multi-machine setting. The central contribution is an enhanced analysis framework extending Albers and Eckl (2020) that improves the deterministic single-machine competitive ratio from 4 to 1 + √2 ≈ 2.4143 and then to 2.316513 via a new algorithm; the randomized expected ratio improves from 3.3794 to 2.152271. Multi-machine extensions via Gong et al. (2024) yield deterministic and randomized ratios of 2.77629 − (0.45977/m) and 2.51098 − (0.3587/m), with the m = 1 case matching the single-machine bounds.

Significance. If the derivations hold, the work advances the state of the art by providing strictly tighter competitive ratios for a natural model of scheduling with uncertainty. The amortization-based framework is a clear technical strength, as is the explicit verification that the multi-machine bounds reduce correctly to the single-machine case. These improvements are non-trivial and could serve as a reference point for subsequent analyses of similar explorable-uncertainty problems.

minor comments (3)
  1. The abstract states precise numerical ratios (e.g., 2.316513) obtained from the new framework; the main text should explicitly display the optimization problem or system of inequalities whose solution produces each constant, so that readers can verify the arithmetic without reconstructing the entire analysis.
  2. Section 1 (Introduction) should restate the modeling choice that testing and processing of a job may occur on different machines before the multi-machine results are presented, to avoid any ambiguity for readers focused on the single-machine case.
  3. A short table comparing the new ratios against all previously published bounds (including the intermediate 1 + √2 value) would improve readability and make the incremental gains immediately visible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No specific major comments appear in the provided report, so we have no individual points requiring point-by-point rebuttal at this stage. We remain available to incorporate any minor changes the editor or referee may identify.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation chain relies on external prior frameworks (Albers and Eckl 2020 for single-machine analysis improvements from 4 to 1+√2 then 2.316513; Gong et al. 2024 for multi-machine extensions) and presents new algorithms whose ratios are outputs of the enhanced analysis, not re-expressions of fitted inputs or self-citations. The m=1 consistency check is an explicit verification step rather than a definitional reduction. No self-definitional equations, fitted predictions renamed as results, or load-bearing self-citations appear; the contribution is an independent tightening of bounds under the stated model.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper operates inside the standard explorable-uncertainty scheduling model; no new free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (1)
  • domain assumption Jobs arrive online with only an upper bound on processing time; testing reveals the true time at a cost.
    This is the core problem definition taken from prior literature and used throughout the claimed results.

pith-pipeline@v0.9.0 · 5853 in / 1279 out tokens · 50733 ms · 2026-05-23T00:32:03.865577+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    By choosing α=1+√5/2 and β=1+√5+√2(7+5√5)/4, the competitive ratio of PCPα,β is 1+√5+√2(7+5√5)/4 ≤2.316513

  • IndisputableMonolith/Constants.lean phi_golden_ratio echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    Corollary 4. By choosing α=β=√2, (α,β)-SORT algorithm is (1+√2)-competitive.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    In: Kaklamanis, C., Levin, A

    Albers, S., Eckl, A.: Explorable uncertainty in scheduling with non-uniform testing times. In: Kaklamanis, C., Levin, A. (eds.) Approximation and Online Algorithms - 18th International Workshop, WAOA 2020, Virtual Event, September 9-10, 2020, Revised Selected Papers. Lecture Notes in Computer Science, vol. 12806, pp. 127–

    work page 2020

  2. [2]

    Springer (2020), https://doi.org/10.1007/978-3-030-80879-2_9

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

  3. [3]

    In: WADS (2021)

    Albers, S., Eckl, A.: Scheduling with testing on multiple identical parallel ma- chines. In: WADS (2021). https://doi.org/10.1007/978-3-030-83508-8 3, https: //doi.org/10.1007/978-3-030-83508-8_3

    work page doi:10.1007/978-3-030-83508-8 2021

  4. [4]

    Morgan Kaufmann Publishers (2017)

    Cardoso, J.M.P., Diniz, P.C., Coutinho, J.G.F.: Embedded computing for high performance: Efficient mapping of computations using customization, code trans- formations and compilation. Morgan Kaufmann Publishers (2017)

    work page 2017

  5. [5]

    In: Benedictis, R.D., Maratea, M., Micheli, A., Scala, E., Serina, I., Vallati, M., Umbrico, A

    Caruso, S., Galat` a, G., Maratea, M., Mochi, M., Porro, I.: Scheduling pre-operative assessment clinic via answer set programming. In: Benedictis, R.D., Maratea, M., Micheli, A., Scala, E., Serina, I., Vallati, M., Umbrico, A. (eds.) Proceedings of the 9th Italian workshop on Planning and Scheduling (IPS’21) and the 28th Inter- national Workshop on ”Expe...

    work page 2021

  6. [6]

    A Geometric Heuristic for Rectilinear Crossing Minimization

    Ding, B., Feng, Y., Ho, C., Tang, W., Xu, H.: Competitive information design for pandora’s box. In: Bansal, N., Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023. pp. 353–381. SIAM (2023), https://doi.org/10.1137/1. 9781611977554.ch15

    work page doi:10.1137/1 2023

  7. [7]

    In: Karlin, A.R

    D¨ urr, C., Erlebach, T., Megow, N., Meißner, J.: Scheduling with explorable un- certainty. In: Karlin, A.R. (ed.) 9th Innovations in Theoretical Computer Sci- ence Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA. LIPIcs, vol. 94, pp. 30:1–30:14. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik (2018), https://doi.org/10.4230/LIPIcs.ITCS.2018.30

    work page doi:10.4230/lipics.itcs.2018.30 2018

  8. [8]

    Algorithmica 82(12), 3630–3675 (2020), https://doi.org/10.1007/ s00453-020-00742-2

    D¨ urr, C., Erlebach, T., Megow, N., Meißner, J.: An adversarial model for scheduling with testing. Algorithmica 82(12), 3630–3675 (2020), https://doi.org/10.1007/ s00453-020-00742-2

    work page 2020

  9. [9]

    Erlebach, T., Hoffmann, M.: Query-competitive algorithms for computing with uncertainty. Bull. EATCS 116 (2015), http://eatcs.org/beatcs/index.php/ beatcs/article/view/335

    work page 2015

  10. [10]

    Erlebach, T., Hoffmann, M., Kammer, F.: Query-competitive algorithms for cheap- est set problems under uncertainty. Theor. Comput. Sci. 613, 51–64 (2016), https://doi.org/10.1016/j.tcs.2015.11.025

    work page doi:10.1016/j.tcs.2015.11.025 2016

  11. [11]

    Esfandiari, H., Hajiaghayi, M.T., Lucier, B., Mitzenmacher, M.: Online pandora’s boxes and bandits. In: The Thirty-Third AAAI Conference on Artificial Intelli- gence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelli- gence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Ad- vances in Artificial Intelligence, EAAI 20...

    work page 2019

  12. [12]

    Feder, T., Motwani, R., O’Callaghan, L., Olston, C., Panigrahy, R.: Computing shortest paths with uncertainty. J. Algorithms 62(1), 1–18 (2007), https://doi. org/10.1016/j.jalgor.2004.07.005

    work page doi:10.1016/j.jalgor.2004.07.005 2007

  13. [13]

    In: Yao, F.F., Luks, E.M

    Feder, T., Motwani, R., Panigrahy, R., Olston, C., Widom, J.: Computing the median with uncertainty. In: Yao, F.F., Luks, E.M. (eds.) Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21-23, 2000, Portland, OR, USA. pp. 602–607. ACM (2000), https://doi.org/10.1145/ 335305.335386

    work page arXiv 2000

  14. [14]

    Algorithmica (2023)

    Gong, M., Chen, Z.Z., Hayashi, K.: Approximation algorithms for multiprocessor scheduling with testing to minimize the total job completion time. Algorithmica (2023). https://doi.org/10.1007/s00453-023-01198-w

    work page doi:10.1007/s00453-023-01198-w 2023

  15. [15]

    Theory Comput

    Gupta, M., Sabharwal, Y., Sen, S.: The update complexity of selection and related problems. Theory Comput. Syst. 59(1), 112–132 (2016), https://doi.org/10. 1007/s00224-015-9664-y

    work page 2016

  16. [16]

    Halld´ orsson, M.M., de Lima, M.S.: Query-competitive sorting with uncertainty. Theor. Comput. Sci. 867, 50–67 (2021), https://doi.org/10.1016/j.tcs.2021. 03.021

    work page doi:10.1016/j.tcs.2021 2021

  17. [17]

    In: Albers, S., Weil, P

    Hoffmann, M., Erlebach, T., Krizanc, D., Mihal´ ak, M., Raman, R.: Comput- ing minimum spanning trees with uncertainty. In: Albers, S., Weil, P. (eds.) STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Sci- ence, Bordeaux, France, February 21-23, 2008, Proceedings. LIPIcs, vol. 1, pp. 277–288. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur In...

    work page doi:10.4230/lipics.stacs.2008.1358 2008

  18. [18]

    In: Koutsougeras, C., Vitter, J.S

    Kahan, S.: A model for data in motion. In: Koutsougeras, C., Vitter, J.S. (eds.) Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA. pp. 267–277. ACM (1991), https://doi. org/10.1145/103418.103449

    work page doi:10.1145/103418.103449 1991

  19. [19]

    In: Byrka, J., Wiese, A

    Liu, A.H., Liu, F., Wong, P.W.H., Zhang, X.: The power of amortiza- tion on scheduling with explorable uncertainty. In: Byrka, J., Wiese, A. (eds.) Approximation and Online Algorithms - 21st International Workshop, WAOA 2023, Amsterdam, The Netherlands, September 7-8, 2023, Proceed- ings. Lecture Notes in Computer Science, vol. 14297, pp. 90–103. Springer...

    work page doi:10.1007/978-3-031-49815-2 2023

  20. [20]

    google.com/file/d/1ELap0SNk9UKZB9tmuRU06bNEMlwxDyxd/view

    Liu, H.H., Liu, F.H., Wong, P.W., Zhang, X.O.: Amortization helps for scheduling with explorable uncertainty, even on parallel machines (2024), https://drive. google.com/file/d/1ELap0SNk9UKZB9tmuRU06bNEMlwxDyxd/view

    work page 2024

  21. [21]

    In: Gusikhin, O., Hammoudi, S., Cuzzocrea, A

    Lopes, J., Vieira, G., Veloso, R., Ferreira, S., Salazar, M., Santos, M.F.: Op- timization of surgery scheduling problems based on prescriptive analytics. In: Gusikhin, O., Hammoudi, S., Cuzzocrea, A. (eds.) Proceedings of the 12th In- ternational Conference on Data Science, Technology and Applications, DATA 2023, Rome, Italy, July 11-13, 2023. pp. 474–47...

    work page doi:10.5220/0012131700003541 2023

  22. [22]

    263–286 (2008)

    Nicolai, R.P., Dekker, R.: Optimal Maintenance of Multi-component Systems: A Review, pp. 263–286 (2008)

    work page 2008

  23. [23]

    In: Abbadi, A.E., Brodie, M.L., Chakravarthy, S., Dayal, U., Kamel, N., Schlageter, G., Whang, K

    Olston, C., Widom, J.: Offering a precision-performance tradeoff for aggregation queries over replicated data. In: Abbadi, A.E., Brodie, M.L., Chakravarthy, S., Dayal, U., Kamel, N., Schlageter, G., Whang, K. (eds.) VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10-14, 2000, Cairo, Egypt. pp. 144–155. Morgan Ka...

    work page 2000

  24. [24]

    Econometrica 47(3), 641–654 (1979), http://www.jstor.org/stable/1910412

    Weitzman, M.L.: Optimal search for the best alternative. Econometrica 47(3), 641–654 (1979), http://www.jstor.org/stable/1910412

    work page arXiv 1979

  25. [25]

    ACM SIGOPS Oper

    Wiseman, Y., Schwan, K., Widener, P.M.: Efficient end to end data exchange using configurable compression. ACM SIGOPS Oper. Syst. Rev. 39(3), 4–23 (2005), https://doi.org/10.1145/1075395.1075396 A Appendix For parallel machines, Gong et al. [13] proposed a framework based on Al- bers and Eckl’s work. When m tends to infinity, the ratio of their algorithm ...

    work page doi:10.1145/1075395.1075396 2005

  26. [26]

    Afterwards, the adversary sets all pj = 0 for all jobs j except job j′, which is any job picked by the adversary from the jobs assigned to time 2(m−1) + 1 or later

    + 1 time. Afterwards, the adversary sets all pj = 0 for all jobs j except job j′, which is any job picked by the adversary from the jobs assigned to time 2(m−1) + 1 or later. Depending on A’s behavior onj′, there are two cases: Case 1: A tests j′. In this case, the adversary sets pj′= 2m, i.e., it makes j′ have the processing time equal to the upper limit...

    work page