Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

Wen-Han Hsieh; Ya-Chun Liang

arxiv: 2604.26349 · v1 · submitted 2026-04-29 · 💻 cs.DS · cs.LG

Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management

Wen-Han Hsieh , Ya-Chun Liang This is my paper

Pith reviewed 2026-05-07 12:46 UTC · model grok-4.3

classification 💻 cs.DS cs.LG

keywords learning-augmented algorithmsonline algorithmsbuffer managementFIFO schedulingpreemptive algorithmscompetitive analysisprediction error metricsasymptotic robustness

0 comments

The pith

A learning-augmented algorithm for preemptive FIFO buffer management is 1-consistent with perfect predictions, degrades smoothly with error, and retains asymptotic √3-competitiveness even with useless predictions.

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

The authors design an online algorithm for packets arriving to a fixed-capacity buffer that must be sent in FIFO order but can be preempted and discarded. The algorithm incorporates predictions of future arrivals and evaluates those predictions only on the subset of packets that actually get transmitted, rather than penalizing for packets that capacity would have rejected anyway. When predictions are perfect the algorithm is exactly 1-competitive; as prediction error grows it degrades in a controlled way; and when predictions are completely wrong it still achieves an asymptotic competitive ratio of √3. This last guarantee matches the best known bound for the same problem without any learning or predictions. The design also shows that any other β-competitive online algorithm can be dropped in as a fallback to obtain asymptotic β-robustness.

Core claim

We present a learning-augmented online algorithm that simultaneously achieves 1-consistency, η-smoothness, and asymptotic √3-robustness for the preemptive FIFO buffer management problem. The algorithm uses an output-based prediction error metric that measures quality only over the packets ultimately transmitted by an optimal schedule, together with a buffer-clearing strategy that switches to a worst-case fallback; the extra cost of clearing is bounded by an additive constant depending only on buffer capacity and therefore vanishes asymptotically. Replacing the fallback module with any β-competitive online algorithm immediately yields asymptotic β-robustness.

What carries the argument

An output-based prediction error metric that scores predictions only on transmitted packets, combined with a dynamic buffer-clearing operation whose extra competitive cost is bounded by an additive capacity constant.

If this is right

With perfect predictions the algorithm is exactly 1-competitive.
Its competitive ratio degrades continuously with the size of the prediction error η.
Under completely inaccurate predictions the asymptotic competitive ratio remains √3, matching the classical bound.
Substituting any other β-competitive online algorithm as the fallback immediately produces asymptotic β-robustness.

Where Pith is reading between the lines

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

The same output-based error metric and bounded-clearing technique could be adapted to other online problems where capacity limits mean only a fraction of inputs are ever processed.
Running the algorithm on real network traces with machine-learned arrival predictions would reveal whether the smoothness property holds for typical rather than worst-case error patterns.
Because the robustness guarantee improves with instance size, the approach is especially attractive for high-speed links where buffer capacities are large relative to packet sizes.
The generalized fallback construction suggests a modular way to retrofit many existing online algorithms with learning augmentation while preserving their proven worst-case ratios.

Load-bearing premise

The extra competitive loss caused by the buffer-clearing operation is bounded by an additive constant that depends only on buffer capacity and becomes negligible for large instances.

What would settle it

A sequence of larger and larger instances under arbitrarily bad predictions in which the competitive ratio stays strictly above √3 + ε for some fixed ε > 0, even after the additive capacity term is divided out, would falsify the asymptotic √3-robustness claim.

read the original abstract

We present a learning-augmented online algorithm for the preemptive FIFO buffer management problem, where packets arrive online to a finite-capacity buffer, must be transmitted in FIFO order, and the algorithm may preemptively discard buffered packets to accommodate future arrivals. Our algorithm simultaneously achieves 1-consistency, \eta-smoothness, and asymptotic \sqrt{3}-robustness, where \eta denotes the prediction error. Specifically, it attains an optimal competitive ratio of 1 under perfect predictions, degrades smoothly as the prediction error increases, and maintains an asymptotic competitive ratio of \sqrt{3} under arbitrarily inaccurate predictions, matching the best-known worst-case guarantee for the classical online problem, established by Englert and Westermann in 2009 [Algorithmica 53(4): 523-548]. A key technical contribution of our work is the introduction of an \emph{output-based prediction error metric}. Because capacity constraints dictate that only a strictly bounded subset of arriving packets is ultimately transmitted, our metric assesses prediction quality over the resulting optimal schedules rather than the raw input sequences, avoiding artificial error penalties. To guarantee robustness, our algorithm dynamically monitors predictions and executes a \emph{buffer-clearing strategy} upon transitioning to a worst-case fallback mechanism. We prove that the competitive loss incurred by this clearing operation is bounded by an additive capacity constant that vanishes asymptotically. Finally, we show that our algorithm provides a generalized framework for learning-augmented buffer management: substituting the fallback module with any \beta-competitive online algorithm immediately yields asymptotic \beta-robustness.

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.

Desk Editor's Note private letter to a colleague

The paper gives a workable template for adding predictions to preemptive FIFO buffer management while recovering the classical asymptotic √3 bound in the limit.

read the letter

The core contribution is an algorithm that is 1-consistent under perfect predictions, η-smooth as error grows, and asymptotically √3-robust even when predictions are useless. It does this by switching to a fallback online algorithm plus a buffer-clearing step, and by measuring prediction error only on the packets that actually get transmitted in the optimal schedule rather than on every arrival. That output-based metric avoids charging the algorithm for packets the buffer could never have kept anyway. The framework is also modular: any β-competitive fallback immediately gives asymptotic β-robustness. These pieces are new relative to the 2009 Englert-Westermann result and to earlier learning-augmented work on buffer problems. The paper is clear about how the pieces fit together and why the classical bound is recovered asymptotically. The clearing cost is claimed to be only an additive O(B) term that becomes negligible, which is the key technical step. If that bound holds under arbitrary prediction sequences, the robustness claim follows directly. The main soft spot is exactly there: the argument that clearings stay infrequent enough and do not accumulate multiplicative overhead depends on the monitoring rule and on how the output-based metric interacts with capacity. The abstract sketches the proof, but the full error analysis would need to show that the number of transitions stays controlled even in adversarial cases. Minor edge cases around simultaneous arrivals or exact capacity exhaustion could also affect the smoothness constants. Readers already working on online algorithms or learning-augmented scheduling will find this useful as a concrete example of how to make robustness asymptotic rather than multiplicative. It is not a foundational result, but it is a clean extension that deserves referee time because the claims are precise, the prior bound is cited correctly, and the new metric is a reasonable adaptation to the capacity constraint. I would send it out for review.

Referee Report

2 major / 2 minor

Summary. The paper presents a learning-augmented online algorithm for preemptive FIFO buffer management. It claims to simultaneously achieve 1-consistency (optimal performance under perfect predictions), η-smoothness (graceful degradation with prediction error η), and asymptotic √3-robustness (matching the best-known classical online competitive ratio from Englert and Westermann 2009 under arbitrary predictions). The key technical contributions are an output-based prediction error metric that evaluates predictions only over packets transmitted in the optimal schedule (to avoid capacity-induced artifacts) and a buffer-clearing strategy that transitions to a fallback algorithm while incurring only an additive O(B) competitive loss that vanishes asymptotically relative to OPT. The work also provides a general framework in which any β-competitive online algorithm can be substituted as the fallback to obtain asymptotic β-robustness.

Significance. If the central claims hold, the result is significant for the learning-augmented algorithms literature. It is the first such result for preemptive FIFO buffer management that preserves the optimal asymptotic competitive ratio while adding consistency and smoothness guarantees. The output-based metric and the additive-loss clearing argument are clever ways to handle finite buffer capacity, and the plug-and-play fallback framework is a reusable contribution. The work correctly credits and builds directly on the 2009 Englert-Westermann bound rather than attempting to improve the worst-case ratio.

major comments (2)

[Buffer-clearing strategy and asymptotic analysis] The asymptotic √3-robustness claim rests on the buffer-clearing strategy incurring only an additive O(B) loss that is o(OPT) in the limit. The manuscript must supply an explicit bound on the number (or total cost) of clearing events under arbitrary predictions; without it, repeated transitions could accumulate a non-vanishing multiplicative factor and prevent the ratio from approaching the Englert-Westermann bound.
[Output-based prediction error metric] The output-based prediction error metric is defined over transmitted packets in the optimal schedule rather than all arrivals. While this avoids artificial penalties, the manuscript must prove that the metric introduces no capacity-dependent multiplicative artifacts into the 1-consistency and η-smoothness bounds; otherwise the claimed guarantees may hold only for specific B or prediction regimes.

minor comments (2)

[Abstract] The abstract states that η denotes the prediction error but does not indicate its normalization or range; a short clarifying sentence would improve readability.
[References] The reference to Englert and Westermann 2009 should include the full bibliographic details (journal, volume, pages) in the bibliography section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The positive assessment of the significance of our contributions is appreciated. We address each major comment below, agreeing that additional details are needed in the analysis to fully substantiate the claims.

read point-by-point responses

Referee: [Buffer-clearing strategy and asymptotic analysis] The asymptotic √3-robustness claim rests on the buffer-clearing strategy incurring only an additive O(B) loss that is o(OPT) in the limit. The manuscript must supply an explicit bound on the number (or total cost) of clearing events under arbitrary predictions; without it, repeated transitions could accumulate a non-vanishing multiplicative factor and prevent the ratio from approaching the Englert-Westermann bound.

Authors: We agree that the current manuscript bounds the loss per clearing event by O(B) but does not explicitly bound the number of clearing events (or total clearing cost) under arbitrary predictions. This leaves open the possibility of accumulation affecting the asymptotic ratio, as noted. In the revision, we will add a lemma in the robustness analysis section that bounds the number of clearing events by O(OPT/B + 1), by charging each clearing to distinct segments of the optimal schedule and using the fact that each clearing frees B units of capacity. This ensures the total additive loss remains o(OPT) and the ratio approaches √3. revision: yes
Referee: [Output-based prediction error metric] The output-based prediction error metric is defined over transmitted packets in the optimal schedule rather than all arrivals. While this avoids artificial penalties, the manuscript must prove that the metric introduces no capacity-dependent multiplicative artifacts into the 1-consistency and η-smoothness bounds; otherwise the claimed guarantees may hold only for specific B or prediction regimes.

Authors: The output-based metric evaluates error only over packets transmitted by OPT, which by definition respects the capacity constraint and avoids penalties from untransmittable packets. However, we acknowledge that an explicit proof is required to rule out B-dependent multiplicative factors in the consistency and smoothness bounds. We will add a dedicated lemma deriving the 1-consistency (ratio exactly 1) and η-smoothness (ratio 1 + O(η)) directly from the metric, showing the bounds hold uniformly for any fixed B without additional multiplicative terms depending on capacity. revision: yes

Circularity Check

0 steps flagged

No significant circularity; asymptotic robustness relies on external 2009 result plus independent proofs

full rationale

The derivation introduces an output-based prediction error metric and buffer-clearing strategy, then proves within the paper that clearing incurs only additive O(B) loss vanishing asymptotically. 1-consistency and η-smoothness follow directly from these definitions and the metric's construction. Asymptotic √3-robustness is obtained by invoking the independently established Englert-Westermann bound (2009, different authors) once the additive term is shown o(OPT); the generalized β-robustness claim is likewise proved by substitution. No equation reduces to a prior fit or self-citation by construction, and no load-bearing premise is justified solely by overlapping-author citations.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard assumptions from online competitive analysis and the existence of a √3-competitive fallback algorithm from prior work. The paper introduces a new metric and strategy without additional fitted parameters.

axioms (1)

domain assumption Existence of a β-competitive online algorithm for preemptive FIFO buffer management that can serve as fallback
Invoked to guarantee asymptotic β-robustness when substituting the fallback module.

invented entities (1)

output-based prediction error metric no independent evidence
purpose: Assess prediction quality over resulting optimal schedules rather than raw input sequences to avoid artificial penalties from capacity constraints
Newly defined metric central to the smoothness and consistency guarantees.

pith-pipeline@v0.9.0 · 5584 in / 1507 out tokens · 69958 ms · 2026-05-07T12:46:34.138341+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

[1]

Competitive queue policies for differentiated services

William A Aiello, Yishay Mansour, S Rajagopolan, and Adi Ros \'e n. Competitive queue policies for differentiated services. Journal of Algorithms , 55(2):113--141, 2005

work page 2005
[2]

Competitive queueing policies for qos switches

Nir Andelman, Yishay Mansour, and An Zhu. Competitive queueing policies for qos switches. In SODA , volume 3, pages 761--770, 2003

work page 2003
[3]

Online bin packing with predictions

Spyros Angelopoulos, Shahin Kamali, and Kimia Shadkami. Online bin packing with predictions. Journal of Artificial Intelligence Research , 78:1111--1141, 2023

work page 2023
[4]

Online metric algorithms with untrusted predictions

Antonios Antoniadis, Christian Coester, Marek Eli \'a s , Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM transactions on algorithms , 19(2):1--34, 2023

work page 2023
[5]

Scheduling with speed predictions

Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei. Scheduling with speed predictions. Theory of Computing Systems , 69(2):16, 2025

work page 2025
[6]

Learning-augmented weighted paging

Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning-augmented weighted paging. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 67--89. SIAM, 2022

work page 2022
[7]

Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko

Nikhil Bansal, Lisa K. Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko. Further improvements in competitive guarantees for qos buffering. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , pages 196--207. Springer, 2004

work page 2004
[8]

Online bin covering with frequency predictions

Magnus Berg and Shahin Kamali. Online bin covering with frequency predictions. arXiv preprint arXiv:2401.14881 , 2024

work page arXiv 2024
[9]

Online time-windows tsp with predictions

Shuchi Chawla and Dimitris Christou. Online time-windows tsp with predictions. arXiv preprint arXiv:2304.01958 , 2023

work page arXiv 2023
[10]

Lower and upper bounds on fifo buffer management in qos switches

Matthias Englert and Matthias Westermann. Lower and upper bounds on fifo buffer management in qos switches. Algorithmica , 53(4):523--548, 2009

work page 2009
[11]

Learning-augmented algorithms for online tsp on the line

Themistoklis Gouleakis, Konstantinos Lakis, and Golnoosh Shahkarami. Learning-augmented algorithms for online tsp on the line. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 11989--11996, 2023

work page 2023
[12]

Online tsp with predictions

Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, and Chung-Shou Liao. Online tsp with predictions. arXiv preprint arXiv:2206.15364 , 2022

work page arXiv 2022
[13]

Online tsp and online dial-a-ride with predictions

Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, and Chung-Shou Liao. Online tsp and online dial-a-ride with predictions. INFORMS Journal on Computing , 2025

work page 2025
[14]

Online knapsack with frequency predictions

Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems , 34:2733--2743, 2021

work page 2021
[15]

Non-clairvoyant scheduling with predictions

Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. ACM Transactions on Parallel Computing , 10(4):1--26, 2023

work page 2023
[16]

Online algorithms for weighted paging with predictions

Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. ACM Transactions on Algorithms (TALG) , 18(4):1--27, 2022

work page 2022
[17]

Competitive snoopy caching

Anna R Karlin, Mark S Manasse, Larry Rudolph, and Daniel D Sleator. Competitive snoopy caching. Algorithmica , 3(1):79--119, 1988

work page 1988
[18]

Improved competitive guarantees for qos buffering

Alex Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guarantees for qos buffering. Algorithmica , 43(1):63--80, 2005

work page 2005
[19]

Buffer overflow management in qos switches

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, and Maxim Sviridenko. Buffer overflow management in qos switches. SIAM Journal on Computing , 33(3):563--583, 2004. https://doi.org/10.1137/S0097539701399666 doi:10.1137/S0097539701399666

work page doi:10.1137/s0097539701399666 2004
[20]

Minimalistic predictions to schedule jobs with online precedence constraints

Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schl \"o ter. Minimalistic predictions to schedule jobs with online precedence constraints. In International Conference on Machine Learning , pages 18563--18583. PMLR, 2023

work page 2023
[21]

Online scheduling via learned weights

Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1859--1877. SIAM, 2020

work page 2020
[22]

Learning-augmented online packet scheduling with deadlines

Ya-Chun Liang, Clifford Stein, and Hao-Ting Wei. Learning-augmented online packet scheduling with deadlines. arXiv preprint arXiv:2305.07164 , 2023

work page arXiv 2023
[23]

Permutation predictions for non-clairvoyant scheduling

Simon Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. arXiv preprint arXiv:2202.10199 , 2022

work page arXiv 2022
[24]

Lykouris and S

T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning (ICML) , pages 3296--3305. PMLR, 2018

work page 2018
[25]

Optimal smoothing schedules for real-time streams

Yishay Mansour, Boaz Patt-Shamir, and Ofer Lapid. Optimal smoothing schedules for real-time streams. Distributed Computing , 17(1):77--89, 2004

work page 2004
[26]

Purohit, Z

M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via machine-learned predictions. Advances in Neural Information Processing Systems (NeurIPS) , 31, 2018

work page 2018
[27]

Amortized efficiency of list update and paging rules

Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM , 28(2):202--208, 1985

work page 1985
[28]

Analysis of queueing policies in qos switches

An Zhu. Analysis of queueing policies in qos switches. Journal of Algorithms , 53(2):137--168, 2004

work page 2004

[1] [1]

Competitive queue policies for differentiated services

William A Aiello, Yishay Mansour, S Rajagopolan, and Adi Ros \'e n. Competitive queue policies for differentiated services. Journal of Algorithms , 55(2):113--141, 2005

work page 2005

[2] [2]

Competitive queueing policies for qos switches

Nir Andelman, Yishay Mansour, and An Zhu. Competitive queueing policies for qos switches. In SODA , volume 3, pages 761--770, 2003

work page 2003

[3] [3]

Online bin packing with predictions

Spyros Angelopoulos, Shahin Kamali, and Kimia Shadkami. Online bin packing with predictions. Journal of Artificial Intelligence Research , 78:1111--1141, 2023

work page 2023

[4] [4]

Online metric algorithms with untrusted predictions

Antonios Antoniadis, Christian Coester, Marek Eli \'a s , Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM transactions on algorithms , 19(2):1--34, 2023

work page 2023

[5] [5]

Scheduling with speed predictions

Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei. Scheduling with speed predictions. Theory of Computing Systems , 69(2):16, 2025

work page 2025

[6] [6]

Learning-augmented weighted paging

Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, and Erik Vee. Learning-augmented weighted paging. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 67--89. SIAM, 2022

work page 2022

[7] [7]

Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko

Nikhil Bansal, Lisa K. Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko. Further improvements in competitive guarantees for qos buffering. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , pages 196--207. Springer, 2004

work page 2004

[8] [8]

Online bin covering with frequency predictions

Magnus Berg and Shahin Kamali. Online bin covering with frequency predictions. arXiv preprint arXiv:2401.14881 , 2024

work page arXiv 2024

[9] [9]

Online time-windows tsp with predictions

Shuchi Chawla and Dimitris Christou. Online time-windows tsp with predictions. arXiv preprint arXiv:2304.01958 , 2023

work page arXiv 2023

[10] [10]

Lower and upper bounds on fifo buffer management in qos switches

Matthias Englert and Matthias Westermann. Lower and upper bounds on fifo buffer management in qos switches. Algorithmica , 53(4):523--548, 2009

work page 2009

[11] [11]

Learning-augmented algorithms for online tsp on the line

Themistoklis Gouleakis, Konstantinos Lakis, and Golnoosh Shahkarami. Learning-augmented algorithms for online tsp on the line. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 37, pages 11989--11996, 2023

work page 2023

[12] [12]

Online tsp with predictions

Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, and Chung-Shou Liao. Online tsp with predictions. arXiv preprint arXiv:2206.15364 , 2022

work page arXiv 2022

[13] [13]

Online tsp and online dial-a-ride with predictions

Hsiao-Yu Hu, Hao-Ting Wei, Meng-Hsi Li, Kai-Min Chung, and Chung-Shou Liao. Online tsp and online dial-a-ride with predictions. INFORMS Journal on Computing , 2025

work page 2025

[14] [14]

Online knapsack with frequency predictions

Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. Advances in Neural Information Processing Systems , 34:2733--2743, 2021

work page 2021

[15] [15]

Non-clairvoyant scheduling with predictions

Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Non-clairvoyant scheduling with predictions. ACM Transactions on Parallel Computing , 10(4):1--26, 2023

work page 2023

[16] [16]

Online algorithms for weighted paging with predictions

Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. ACM Transactions on Algorithms (TALG) , 18(4):1--27, 2022

work page 2022

[17] [17]

Competitive snoopy caching

Anna R Karlin, Mark S Manasse, Larry Rudolph, and Daniel D Sleator. Competitive snoopy caching. Algorithmica , 3(1):79--119, 1988

work page 1988

[18] [18]

Improved competitive guarantees for qos buffering

Alex Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guarantees for qos buffering. Algorithmica , 43(1):63--80, 2005

work page 2005

[19] [19]

Buffer overflow management in qos switches

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, and Maxim Sviridenko. Buffer overflow management in qos switches. SIAM Journal on Computing , 33(3):563--583, 2004. https://doi.org/10.1137/S0097539701399666 doi:10.1137/S0097539701399666

work page doi:10.1137/s0097539701399666 2004

[20] [20]

Minimalistic predictions to schedule jobs with online precedence constraints

Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schl \"o ter. Minimalistic predictions to schedule jobs with online precedence constraints. In International Conference on Machine Learning , pages 18563--18583. PMLR, 2023

work page 2023

[21] [21]

Online scheduling via learned weights

Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online scheduling via learned weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1859--1877. SIAM, 2020

work page 2020

[22] [22]

Learning-augmented online packet scheduling with deadlines

Ya-Chun Liang, Clifford Stein, and Hao-Ting Wei. Learning-augmented online packet scheduling with deadlines. arXiv preprint arXiv:2305.07164 , 2023

work page arXiv 2023

[23] [23]

Permutation predictions for non-clairvoyant scheduling

Simon Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. arXiv preprint arXiv:2202.10199 , 2022

work page arXiv 2022

[24] [24]

Lykouris and S

T. Lykouris and S. Vassilvitskii. Competitive caching with machine learned advice. In Proceedings of the 35th International Conference on Machine Learning (ICML) , pages 3296--3305. PMLR, 2018

work page 2018

[25] [25]

Optimal smoothing schedules for real-time streams

Yishay Mansour, Boaz Patt-Shamir, and Ofer Lapid. Optimal smoothing schedules for real-time streams. Distributed Computing , 17(1):77--89, 2004

work page 2004

[26] [26]

Purohit, Z

M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via machine-learned predictions. Advances in Neural Information Processing Systems (NeurIPS) , 31, 2018

work page 2018

[27] [27]

Amortized efficiency of list update and paging rules

Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM , 28(2):202--208, 1985

work page 1985

[28] [28]

Analysis of queueing policies in qos switches

An Zhu. Analysis of queueing policies in qos switches. Journal of Algorithms , 53(2):137--168, 2004

work page 2004