提出新型学习增强与随机化算法，优化线上延迟聚合问题。
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
- 结合学习建议与随机策略，设计高效在线算法。
- 随机算法竞争力达$e+1$，优于原有$5$-竞争基准。
- 理论与实验结合，验证算法在真实场景的优越性。
本文研究线性度量空间上的学习增强型与随机化在线聚合延迟问题。针对给定的在线服务长度建议，评估算法的鲁棒性与一致性。对于任意$λ∈(0,1]$，我们首先提出一个确定性学习增强的 extsc{Balance}算法，其鲁棒性为$(4/λ+1/λ^2)$，一致性为$(4+λ)$。此外，我们设计了一个经典对抗模型下的随机算法，对盲区对手具有$(e+1)$-竞争力，优于先前确定性$5$-竞争力的 extsc{Balance}基准。值得注意的是，该竞争力甚至低于确定性算法的下界$4$。同时，我们建立了随机算法竞争力的下界为$e$，高于此前的$e/(e-1)$。进一步地，融合两种思想，得到一个随机学习增强算法，具备$(e/λ+1/λ^2)$-鲁棒性与$(e+λ)$-一致性。最后，通过数值实验补充理论分析，评估算法的实证性能。
原文摘要 · Abstract (English)
This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each $λ\in (0,1]$, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is $(4/λ+1/λ^2)$-robust and $(4+λ)$-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is $(e+1)$-competitive against an oblivious adversary, improving over the deterministic $5$-competitive \textsc{Balance} benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of $4$ for deterministic online algorithms. Moreover, we establish a lower bound of $e$ on the competitive ratio of randomized online algorithms, improving the previous lower bound of $e/(e-1)$. Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is $(e/λ+1/λ^2)$-robust and $(e+λ)$-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。