지연이 있는 선형 집계 문제에 대한 학습 기반 및 확률적 알고리즘

Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

본 논문에서는 지연이 발생하는 선형 메트릭 환경에서의 학습 기반 및 확률적 온라인 집계 문제를 연구합니다. 우리는 실시간으로 제공되는 서비스 길이 제안을 조언으로 활용하며, 제안된 알고리즘의 강건성(robustness)과 일관성(consistency)을 평가합니다. 각 $λ ext{∈} (0,1]$에 대해, 먼저 (4/λ+1/λ²)-강건성과 (4+λ)-일관성을 갖는 결정론적 학습 기반 extsc{Balance} 알고리즘을 제안합니다. 또한, 고전적인 적대적 모델에서 이 문제를 해결하기 위한 확률적 알고리즘을 제안하며, 이는 무지한 적대자에 대해 (e+1)의 경쟁률을 가지며, 결정론적이고 5의 경쟁률을 갖는 extsc{Balance} 기준~ ex[cite]{bienkowski2013chain}보다 우수합니다. 주목할 점은 이 경쟁률이 결정론적 온라인 알고리즘에 대한 하한인 4보다 더 낮다는 것입니다. 또한, 확률적 온라인 알고리즘의 경쟁률에 대한 하한을 e로 설정하여 이전의 하한인 e/(e-1)보다 개선했습니다. 더욱이, 두 가지 아이디어를 결합하여 (e/λ+1/λ²)-강건성과 (e+λ)-일관성을 갖는 확률적 학습 기반 알고리즘을 얻었습니다. 마지막으로, 이론적 분석을 보완하고 제안된 알고리즘의 실증적 성능을 평가하기 위해 수치 실험을 수행했습니다.

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.