# Learning-Augmented Online Packet Scheduling with Deadlines

arXiv: https://arxiv.org/abs/2305.07164 · HTML: https://mlsanity.com/paper/2305.07164/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 11 May 2023.

## Builds on (most cited first, 14 of 14)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Scheduling with Predictions and the Price of Misprediction](https://mlsanity.com/paper/1902.00732/) (2019)
- [Learning Augmented Energy Minimization via Speed Scaling](https://mlsanity.com/paper/2010.11629/) (2020)
- [Online Graph Algorithms with Predictions](https://mlsanity.com/paper/2112.11831/) (2021)
- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [A Novel Prediction Setup for Online Speed-Scaling](https://mlsanity.com/paper/2112.03082/) (2021)
- [A Universal Error Measure for Input Predictions Applied to Online Graph Problems](https://mlsanity.com/paper/2205.12850/) (2022)
- [Learning-Augmented Algorithms for Online Steiner Tree](https://mlsanity.com/paper/2112.05353/) (2021)
- [Scheduling with Speed Predictions](https://mlsanity.com/paper/2205.01247/) (2022)
- [An Empirical Study of Online Packet Scheduling Algorithms](https://mlsanity.com/paper/1603.07947/) (2016)
- [Online Packet Scheduling with Bounded Delay and Lookahead](https://mlsanity.com/paper/1606.09395/) (2016)

## Built on by (most cited first, 3 of 3)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Asymptotically Robust Learning-Augmented Algorithms for Preemptive FIFO Buffer Management](https://mlsanity.com/paper/2604.26349/) (2026)
- [Online Packet Scheduling with Deadlines and Learning](https://mlsanity.com/paper/2606.00835/) (2026)

## Abstract (arXiv)

The modern network aims to prioritize critical traffic over non-critical traffic and effectively manage traffic flow. This necessitates proper buffer management to prevent the loss of crucial traffic while minimizing the impact on non-critical traffic. Therefore, the algorithm's objective is to control which packets to transmit and which to discard at each step. In this study, we initiate the learning-augmented online packet scheduling with deadlines and provide a novel algorithmic framework to cope with the prediction. We show that when the prediction error is small, our algorithm improves the competitive ratio while still maintaining a bounded competitive ratio, regardless of the prediction error.