Pith.

Data Structures and Algorithms · arXiv:2611.17083 v1 · submitted 12 Nov 2026 · 28 references

List Update with Time Windows and Delays without Batch-Serving

Icey Siyi Ai, Jingwei Li, Clifford Stein

The paper says

“We study list update with time windows and delays when every request requires a separate access.”

more of the abstract

Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most k ≥ 2, our deterministic First-Element Removal algorithm is (3−2/k)-competitive, hence 3-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is 7/4-competitive on arbitrary 2-overlap inputs. More generally, on inputs without self-overlap, it is (13/4−9/[2(k + 1)])-competitive for every k ≥ 2. For delays, we give a deterministic 5-competitive algorithm and a lower bound of 2 + √3 for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

from the abstract

Pith says

Machine review · deepseek-v4-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

It can be wrong. Challenge this review or reply to it.

the referee pass did not run

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 28 references say.

What would settle it

Construct a concrete 2-overlap input with self-overlap (e.g., two requests to the same element with overlapping windows, and a third request to a different element whose window overlaps both). Apply Lemma 4.4 to obtain a transformed input without self-overlap. Compute the optimal offline cost for both inputs. If the optimal cost for the transformed input is strictly less than for the original, then the inequality OPT(σ') ≤ OPT(σ) is strict, and the competitive ratio bound for the transformed input may not imply the same bound for the original. More importantly, check whether the optimal schedule for the transformed input can be mapped back to a feasible schedule for the original input with the same cost. If not, the analysis is incomplete.

from the skeptic's reading

How the review went

2 readings by deepseek-v4-flash · 13 Nov 2026

  1. Reader holds up confidence moderate
  2. Skeptic partly agrees: says it holds up only with conditions 11 s · 29,471 tokens read, 854 written WBIT's 7/4-competitive guarantee for all 2-overlap inputs relies on Lemma 4.4, whose transformation may alter OPT's schedule in a way that invalidates the potential-function analysis.

Not run on this paper: the referee, the editor, the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The strongest objection

The paper's headline randomized result is that WBIT is 7/4-competitive on all 2-overlap inputs, removing the no-self-overlap assumption that is required for general k. This is achieved via Lemma 4.4, which transforms a 2-overlap input with self-overlap into one without self-overlap, preserving WBIT's cost and not increasing OPT's cost. The transformation works by shifting the release time of one of two overlapping requests to the same element to a later time c, chosen to be after the earlier deadline but before the later deadline, and such that no third request's window intersects the interval [b,c]. The load-bearing concern is that the transformation may change the set of feasible offline schedules in a way that the potential-function analysis of Section 4.1 (which assumes no self-overlap) no longer applies to the transformed input. Specifically, the transformation may create a situation where the offline schedule serves the two requests to the same element in a different order, or at different times, than in the original input, potentially invalidating the accounting of pre-service intervals and the µ and ν accounts. The paper argues that the transformation does not increase OPT's cost, but it does not prove that the optimal offline schedule for the transformed input is the same as the one used in the analysis. The analysis of WBIT in Section 4.1 relies on a fixed optimal schedule that is independent of the random bits. If the transformation changes the optimal schedule, the potential-function analysis may not hold. The paper does not provide a proof that the transformation preserves the structure of the optimal schedule in a way that is compatible with the analysis.

The reader's weakest_assumption correctly identifies that the WBIT guarantee for general k depends on the no-self-overlap assumption, and that for k=2 this assumption is removed via Lemma 4.4. However, the reader does not identify a specific load-bearing concern with Lemma 4.4 itself. The stress-test reveals that Lemma 4.4 is the linchpin of the 7/4 result, and its proof has a subtle gap: the transformation may alter the structure of the optimal offline schedule in a way that is not accounted for in the potential-function analysis. The paper argues that the transformation does not increase OPT's cost, but it does not argue that the optimal schedule for the transformed input is compatible with the analysis (which assumes a fixed optimal schedule independent of the random bits). The concrete test would settle whether this gap is real. If the test shows that the transformation can change the optimal schedule in a way that breaks the analysis, then the 7/4 result is not fully proven. If the test shows that the transformation always preserves the relevant structure, then the result stands. The verdict should be CONDITIONAL: accept subject to the authors providing a rigorous justification that Lemma 4.4 preserves the applicability of the potential-function analysis, or providing an alternative proof that does not rely on the transformation.

Pith's reading of the paper (a machine's summary, not the authors')

The classical list update problem asks an algorithm to keep a list ordered and to serve requests for elements at a cost equal to their position in the list. This paper studies a relaxation where requests are not served immediately but within time windows or at a delay penalty. Unlike an earlier batch-serving model, here every request must be served by its own access, even if several requests arrive for the same element. Serving one request can move that element to the front of the list, so the order in which the algorithm serves overlapping requests becomes part of the decision.

The paper proposes a deterministic algorithm called First-Element Removal, which only serves a request early if its element is already at the head of the list, and otherwise serves at the deadline. This algorithm is 3-competitive in general and achieves the optimal 2-competitive ratio for inputs with overlap at most 2. A randomized variant of the classical BIT rule, called WBIT, serves requests at deadlines and flips a coin to decide whether to move the element to the front. WBIT is 7/4-competitive on all 2-overlap inputs, which is below the deterministic lower bound of 2, and it achieves a constant ratio for general overlap when requests to the same element do not overlap in time.

For the delay model, the paper gives a deterministic algorithm called Delayed Move-to-Front, which serves an element when its accumulated delay reaches two-thirds of its current position. This algorithm is 5-competitive. The paper also proves a lower bound of about 3.73 for any deterministic delay-unaware algorithm, showing that the new setting is harder than the classical one, where the optimal ratio is 2.

Core claim. Theorem 3.2 states that for every k>=2 and every k-overlap input, FER(σ) ≤ (3 - 2/k) OPT(σ). If correct, this gives a deterministic 3-competitive algorithm for the NBA list update problem with time windows, and an optimal 2-competitive guarantee for the 2-overlap case. The paper also claims WBIT is 7/4-competitive on all 2-overlap inputs and (13/4 - 9/(2(k+1)))-competitive on k-overlap inputs without self-overlap, and that DMF is 5-competitive for the delay model.

The premise it rests on. The WBIT guarantee for general k depends on the no-self-overlap assumption, meaning that time windows of requests to the same element must be disjoint (Section 4.1). This assumption is removed only for the special case k=2 via the transformation in Lemma 4.4. If real workloads have self-overlap (multiple requests to the same item with overlapping windows), the randomized guarantee degrades to the deterministic 3-competitive bound, and the separation from the deterministic lower bound of 2 is lost. The delay model also assumes delay functions are nondecreasing, eventually divergent, and zero at release, and the 5-competitive bound for the delay-aware case additionally assumes left-continuity.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

We study list update with time windows and delays when every request requires a separate access. Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. For time windows of overlap at most k ≥ 2, our deterministic First-Element Removal algorithm is (3−2/k)-competitive, hence 3-competitive in general. Against an oblivious adversary, a randomized adaptation of BIT is 7/4-competitive on arbitrary 2-overlap inputs. More generally, on inputs without self-overlap, it is (13/4−9/[2(k + 1)])-competitive for every k ≥ 2. For delays, we give a deterministic 5-competitive algorithm and a lower bound of 2 + √3 for deterministic delay-unaware algorithms. Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-11-14

The authors' main claim, as the classifier picked it out 0.99

“For time windows of overlap at most $k\ge2$, our deterministic First-Element Removal algorithm is $(3-2/k)$-competitive, hence $3$-competitive in general.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.41 · human participants 0.02 · controlled comparison 0.19 · randomized assignment 0.05 · states quantitative result 0.99 · compares with prior results 0.81 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v1). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
We study list update with time windows and delays when every request requires a separate access. contribution 0.57 0.77 0.05 asserted 0.90
Unlike batch-serving models, serving several requests to one element still incurs one access per request, and each access may change the list for subsequent requests. background 0.93 0.17 0.05 asserted 0.83
For time windows of overlap at most $k\ge2$, our deterministic First-Element Removal algorithm is $(3-2/k)$-competitive, hence $3$-competitive in general. result 0.99 0.95 0.44 asserted 1.00
Against an oblivious adversary, a randomized adaptation of BIT is $7/4$-competitive on arbitrary $2$-overlap inputs. result 0.99 0.90 0.10 asserted 1.00
More generally, on inputs without self-overlap, it is $\left(13/4-9/[2(k+1)]\right)$-competitive for every $k\ge2$. result 1.00 0.93 0.12 asserted 1.00
For delays, we give a deterministic $5$-competitive algorithm and a lower bound of $2+\sqrt3$ for deterministic delay-unaware algorithms. result 0.96 0.95 0.15 asserted 1.00
Our analyses extend inversion potentials with per-request credits that reconcile different service times and orders. method 0.89 0.93 0.06 asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.96 · evidence from proof or derivation 1.00

What was examined, and what was not

Sources read

  • arXiv listing abstract v1

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-11-14: 1 request, 5,572 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

References (28)
  1. [1] Albers, S.: Improved randomized on-line algorithms for the list update problem. SIAM Journal on Computing27(3), 682–693 (1998). https://doi.org/10.1137/S0097539794277858,https:// doi.org/10.1137/S0097539794277858 on Pithdoi:10.1137/s0097539794277858
  2. [2] Albers, S., Janke, M.: New bounds for randomized list update in the paid exchange model. In: 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020) on Pith
  3. [3] Albers, S., Von Stengel, B., Werchner, R.: A combined bit and timestamp algorithm for the list update problem. Information Processing Letters56(3), 135–139 (1995) on Pith
  4. [4] Ambühl, C., Gärtner, B., von Stengel, B.: A new lower bound for the list up- date problem in the partial cost model. Theoretical Computer Science268(1), 3– 16 (2001). https://doi.org/https://doi.org/10.1016/S0304-3975(00)00257-7,https://www. sciencedirect.com/science/article/p... on Pithdoi:10.1016/s0304-3975(00)00257-7
  5. [5] Ashlagi, I., Azar, Y., Charikar, M., Chiplunkar, A., Geri, O., Kaplan, H., Makhijani, R., Wang, Y., Wattenhofer, R.: Min-cost bipartite perfect matching with delays. Approxima- tion, Randomization, and Combinatorial Optimization. Algorithms and Techniques (AP- PROX/RANDOM 2017... on Pith
  6. [6] Azar, Y., Chiplunkar, A., Kutten, S., Touitou, N.: Set cover with delay – clairvoyance is not required (2020),https://arxiv.org/abs/1807.08543 on PithPith's reviewarXiv
  7. [7] Azar, Y., Ganesh, A., Ge, R., Panigrahi, D.: Online service with delay. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pp. 551–563 (2017) on Pith
  8. [8] Azar, Y., Lewkowicz, S., Vainstein, D.: List update with delays or time windows. In: 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 297, pp. 15:1–15:20. Schloss Dagstuhl – Leib... on Pithdoi:10.4230/lipics.icalp.2024.15
  9. [9] Azar, Y., Touitou, N.: General framework for metric optimization problems with delay or with deadlines. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). pp. 60–71. IEEE (2019) on Pith
  10. [10] Basiak, M., Bienkowski, M., Böhm, M., Chrobak, M., Jeż, Ł., Sgall, J., Tatarczuk, A.: A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs. In: Benoit, A., Kaplan, H., Wild, S., Herman, G. (eds.) 33rd Annual European Sympo- sium on Algorithms (ESA 2025). Le... on Pithdoi:10.4230/lipics.esa.2025.76
  11. [11] Bienkowski, M., Böhm, M., Byrka, J., Marcinkowski, J.: Online facility location with linear delay. arXiv preprint arXiv:2110.15155 (2021) on PithPith's reviewarXiv
  12. [12] Bienkowski, M., Kraska, A., Schmidt, P.: A match in time saves nine: Deterministic online matching with delays. In: International Workshop on Approximation and Online Algorithms. pp. 132–146. Springer (2017) on Pith
  13. [13] Carrasco, R.A., Pruhs, K., Stein, C., Verschae, J.: The online set aggregation prob- lem. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018: The- oretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. ... on Pithdoi:10.1007/978-3-319-77404-6_19
  14. [14] Coester, C.: Transposition is nearly optimal for IID list update (2026),https://arxiv.org/ abs/2603.10244 on PithPith's reviewarXiv
  15. [15] Deryckere, L., Umboh, S.W.: Online matching with set and concave delays. arXiv preprint arXiv:2211.02394 (2022) on PithPith's reviewarXiv
  16. [16] El-Yaniv, R.: There are infinitely many competitive-optimal online list accessing algorithms. Hebrew University of Jerusalem (1996) 26 on Pith
  17. [17] Gupta, A., Kumar, A., Panigrahi, D.: Caching with time windows and delays. SIAM Journal on Computing51(4), 975–1017 (2022). https://doi.org/10.1137/20M1346286,https://doi. org/10.1137/20M1346286 on Pithdoi:10.1137/20m1346286
  18. [18] Irani, S.: Tworesultsonthelistupdateproblem.InformationProcessingLetters38(6), 301–306 (1991) on Pith
  19. [19] Kamali, S., López-Ortiz, A.: A survey of algorithms and models for list update. In: Space- Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pp. 251–266. Springer (2013) on Pith
  20. [20] Mari, M., Pawłowski, M., Ren, R., Sankowski, P.: Online matching with delays and stochastic arrival times. arXiv preprint arXiv:2210.07018 (2022) on PithPith's reviewarXiv
show 8 more
  1. [21] Mari, M., Pawłowski, M., Ren, R., Sankowski, P.: Online multi-level aggregation with delays and stochastic arrivals (2024),https://arxiv.org/abs/2404.09711 on PithPith's reviewarXiv
  2. [22] McCabe, J.: On serial files with relocatable records. Operations Research13(4), 609–618 (1965) on Pith
  3. [23] Mizgerd, C.: Transposition achieves OPT+o(1)in polynomial time for IID list update (2026), https://arxiv.org/abs/2609.28397 on PithPith's reviewarXiv
  4. [24] Reingold, N., Westbrook, J.: Off-line algorithms for the list update problem. Information Processing Letters60(2), 75–80 (1996). https://doi.org/https://doi.org/10.1016/S0020- 0190(96)00144-5,https://www.sciencedirect.com/science/article/pii/ S0020019096001445 on Pithdoi:10.1016/s0020-
  5. [25] Reingold, N., Westbrook, J., Sleator, D.D.: Randomized competitive algorithms for the list update problem. Algorithmica11(1), 15–32 (1994) on Pith
  6. [26] Schulz, F.: Two new families of list update algorithms. In: International Symposium on Algo- rithms and Computation. pp. 100–109. Springer (1998) on Pith
  7. [27] Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM28(2), 202–208 (feb 1985). https://doi.org/10.1145/2786.2793,https://doi.org/10. 1145/2786.2793 on Pithdoi:10.1145/2786.2793
  8. [28] Teia, B.: A lower bound for randomized list update algorithms. Information Processing Letters 47(1), 5–9 (1993). https://doi.org/https://doi.org/10.1016/0020-0190(93)90150-8,https:// www.sciencedirect.com/science/article/pii/0020019093901508 27 A Omitted Material from Section ... on Pithdoi:10.1016/0020-0190(93)90150-8

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment