本論文研究具搶占機制之線上先進先出緩衝區管理問題（preemptive FIFO buffer management problem）。在此問題中，每個時間點可能有多個封包以線上方式到達容量有限的緩衝區。演算法必須在未知未來輸入的情況下，即時決定是否接受或丟棄每個封包。所有已接受的封包必須依照先進先出的順序進行傳輸。演算法亦可透過搶占機制丟棄已存在於緩衝區的封包，以容納新到達的封包。此問題的目標是在固定緩衝區容量下，最大化成功傳輸封包的總價值。本論文提出一個具一致性與漸近穩健性的擴增學習線上演算法，並給出一個取決於預測誤差及演算法所得價值的競爭比上界。當預測完全正確時，演算法可達到最佳競爭比 1，並獲得與已知完整輸入之離線最佳演算法相同的收益。即使預測任意失準，演算法仍可維持漸近競爭比 √3，此結果在漸近意義下與該問題目前已知的最佳最壞情況保證相符。本論文的另一項技術貢獻是提出一個針對此問題設計的輸出導向預測誤差指標。由於緩衝區容量有限，最終只有部分到達的封包會被傳輸，許多未被傳輸的封包不會影響最終目標。因此，本研究不直接衡量完整的實際輸入序列與預測輸入序列之間的差異。所提出的誤差指標包含兩個部分。第一部分衡量實際輸入與預測輸入所對應之離線最佳排程在封包選擇上的差異。第二部分衡量預測最佳排程所選之封包預測價值與實際價值之間的差異。此設計可避免將不影響最終傳輸結果的封包差異納入誤差，並反映封包價值預測偏差對線上決策的影響。為了避免錯誤預測使演算法效能大幅下降，演算法會動態檢查預測是否影響效能。當預測變得不可靠時，演算法會先清空目前緩衝區中的封包，再切換至具有最壞情況保證的後備線上演算法。本論文證明，清空緩衝區所造成的額外損失至多為一個由緩衝區容量與封包價值上限決定的加法常數。隨著演算法的總價值增加，此損失的相對影響趨近於零，因此不影響漸近穩健性。最後，所提出的演算法亦可作為通用的擴增學習緩衝區管理框架。將後備模組替換為任意競爭比為 β 的線上演算法，所得框架可保證其漸近競爭比不超過 β，並維持一致性及相應的誤差相依效能保證。

We propose a learning-augmented online algorithm for the preemptive FIFO buffer management problem. In this problem, multiple packets may arrive online at each time step to a finite-capacity buffer. Without knowing future inputs, the algorithm must immediately decide whether to accept or discard each packet. All accepted packets must be transmitted in FIFO order. The algorithm may also preemptively discard buffered packets to accommodate new arrivals. The objective is to maximize the total value of eventually transmitted packets under a fixed buffer capacity. Our algorithm achieves 1-consistency and asymptotic √3-robustness while providing an error-dependent performance guarantee. Under perfect predictions, the algorithm achieves the optimal competitive ratio of 1 and obtains the same value as the offline optimal algorithm. Its competitive ratio is bounded in terms of the prediction error η and the value achieved by the algorithm. Even when the predictions are arbitrarily inaccurate, the algorithm maintains an asymptotic competitive ratio of √3. This matches the best-known worst-case guarantee for the classical online problem asymptotically [1].
Another technical contribution of this work is an output-level prediction error measure designed for this problem. Since the buffer has limited capacity, only a subset of the arriving packets can eventually be transmitted, and many packets that are not transmitted have no effect on the final objective. We therefore do not directly measure the difference between the complete actual and predicted input sequences. Instead, the proposed error measure consists of two components. The first measures the difference in packet selection between the offline optimal schedules for the actual and predicted instances. The second measures the difference between the predicted and true values of the packets selected by the predicted optimal schedule. This design avoids counting errors on packets that do not affect the final transmitted output and captures the effect of packet-value prediction errors on online decisions. To prevent inaccurate predictions from causing substantial performance loss, the algorithm dynamically checks whether the predictions are affecting its performance. When the predictions become unreliable, the algorithm clears its current buffer and switches to a fallback online algorithm with a worst-case guarantee. We prove that the additional loss caused by clearing the buffer is bounded by an additive constant determined by the buffer capacity and the maximum packet value. As the total value obtained by the algorithm increases, the relative effect of this loss approaches zero and therefore does not affect the asymptotic robustness guarantee. Finally, the proposed algorithm provides a general framework for learning-augmented buffer management. Replacing the fallback module with any β-competitive online algorithm guarantees an asymptotic competitive ratio of at most β while preserving 1-consistency and the corresponding error-dependent performance guarantee.

[1] Matthias Englert and Matthias Westermann. Lower and upper bounds on fifo buffer management in qos switches. Algorithmica, 53(4):523–548, 2009.
[2] Alex Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guarantees for qos buffering. Algorithmica, 43(1):63–80, 2005.
[3] Daniel D Sleator and Robert E Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202–208, 1985.
[4] Anna R Karlin, Mark S Manasse, Larry Rudolph, and Daniel D Sleator. Competitive snoopy caching. Algorithmica, 3(1):79–119, 1988.
[5] 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.
[6] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018.
[7] A. Rohatgi. The power of learning-augmented online algorithms. Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 1–13, 2022.
[8] William A Aiello, Yishay Mansour, S Rajagopolan, and Adi Ros ´en. Competitive queue policies for differentiated services. Journal of Algorithms, 55(2):113–141, 2005.
[9] 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.
[10] Yishay Mansour, Boaz Patt-Shamir, and Ofer Lapid. Optimal smoothing schedules for real-time streams. Distributed Computing, 17(1):77–89, 2004.
[11] Nir Andelman, Yishay Mansour, and An Zhu. Competitive queueing policies for qos switches. In SODA, volume 3, pages 761–770, 2003.
[12] An Zhu. Analysis of queueing policies in qos switches. Journal of Algorithms, 53(2):137–168, 2004.
[13] Nikhil Bansal, Lisa K. Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko. Further improvements in competitive guarantees for qos buffer-ing. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), pages 196–207. Springer, 2004
[14] Kamal Al-Bawani, Matthias Englert, and Matthias Westermann. Comparison-based fifo buffer management in qos switches. In LATIN 2016: Theoretical Informatics, pages 27–40. Springer, 2016.
[15] Yossi Azar and Oren Gilon. Buffer management for packets with processing times. In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 47–58. Springer, 2015.
[16] Yi-Hua Yang, Chung-Shou Liao, Xin Han, and Louxin Zhang. Online buffer manage-ment for transmitting packets with processing cycles. Theoretical Computer Science, 723:73–83, 2018.
[17] Bruce Hajek. On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings of the 2001 Conference on Information Sciences and Systems, 2001.
[18] Francis YL Chin and Stanley PY Fung. Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica (New York), 2003.
[19] Marek Chrobak, Wojciech Jawor, Jiˇr´ı Sgall, and Tom ´a ˇs Tich `y. Improved online al-gorithms for buffer management in qos switches. ACM Transactions on Algorithms (TALG), 3(4):50–es, 2007.
[20] Fei Li, Jay Sethuraman, and Clifford Stein. An optimal online algorithm for packet scheduling with agreeable deadlines. In SODA, volume 5, pages 801–802, 2005.
[21] Fei Li, Jay Sethuraman, and Clifford Stein. Better online buffer management. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 199–208, 2007.
[22] Matthias Englert and Matthias Westermann. Considering suppressed packets improves buffer management in quality of service switches. SIAM Journal on Computing, 41(5):1166–1192, 2012.
[23] Pavel Vesel `y, Marek Chrobak, Łukasz Je ˙z, and Jiˇr´ı Sgall. A ϕ-competitive algorithm for scheduling packets with deadlines. SIAM Journal on Computing, 51(5):1626–1691, 2022.
[24] Łukasz Je ˙z, Fei Li, Jay Sethuraman, and Clifford Stein. Online scheduling of packets with agreeable deadlines. ACM Transactions on Algorithms (TALG), 9(1):1–11, 2012.
[25] Francis YL Chin, Marek Chrobak, Stanley PY Fung, Wojciech Jawor, Jiˇr´ı Sgall, and Tom ´a ˇs Tich `y. Online competitive algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms, 4(2):255–276, 2006.
[26] Martin B ¨ohm, Marek Chrobak, Łukasz Je ˙z, Fei Li, Jiˇr´ı Sgall, and Pavel Vesel `y. Online packet scheduling with bounded delay and lookahead. Theoretical Computer Science,776:95–113, 2019.
[27] Edward F Grove. Online bin packing with lookahead. In Proceedings of the sixth annual ACM-SIAM symposium on discrete algorithms, pages 430–436, 1995.
[28] Susanne Albers. On the influence of lookahead in competitive paging algorithms. Algorithmica, 18(3):283–305, 1997.
[29] Rajeev Motwani, Vijay Saraswat, and Eric Torng. Online scheduling with lookahead: Multipass assembly lines. INFORMS Journal on Computing, 10(3):331–340, 1998.
[30] Koji M Kobayashi. An optimal algorithm for 2-bounded delay buffer management with lookahead. Theoretical Computer Science, 896:65–78, 2021.
[31] Simon Lindermayr and Nicole Megow. Permutation predictions for non-clairvoyant scheduling. arXiv preprint arXiv:2202.10199, 2022.
[32] 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.
[33] Ya-Chun Liang, Clifford Stein, and Hao-Ting Wei. Learning-augmented online packet scheduling with deadlines. arXiv preprint arXiv:2305.07164, 2023.
[34] Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei. Scheduling with speed predictions. Theory of Computing Systems, 69(2):16, 2025.
[35] Zhihao Jiang, Debmalya Panigrahi, and Kevin Sun. Online algorithms for weighted paging with predictions. ACM Transactions on Algorithms (TALG), 18(4):1–27, 2022.
[36] 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.
[37] 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.
[38] Shuchi Chawla and Dimitris Christou. Online time-windows tsp with predictions. arXiv preprint arXiv:2304.01958, 2023.
[39] 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.
[40] 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.
[41] Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schl ¨oter. Minimalistic predictions to schedule jobs with online precedence constraints. In Inter-national Conference on Machine Learning, pages 18563–18583. PMLR, 2023.
[42] 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.
[43] Spyros Angelopoulos, Shahin Kamali, and Kimia Shadkami. Online bin packing with predictions. Journal of Artificial Intelligence Research, 78:1111–1141, 2023
[44] Magnus Berg and Shahin Kamali. Online bin covering with frequency predictions. arXiv preprint arXiv:2401.14881, 2024.
[45] 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.
[46] 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.
[47] Alexander Lindermayr, Nicole Megow, and Bertrand Simon. Double Coverage with Machine-Learned Advice. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Pro-ceedings in Informatics (LIPIcs), pages 99:1–99:18, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik