Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis
In this paper, we present improved learning-augmented algorithms for the multi-option ski rental problem. Learning-augmented algorithms take ML predictions as an added part of the input and incorporates these predictions…
FedQueue: Queue-Aware Federated Learning for Cross-Facility HPC Training
Federated learning (FL) across multiple HPC facilities faces stochastic admission delays from batch schedulers that dominate wall-clock time. Synchronous FL suffers from severe stragglers, while asynchronous FL accumulat…
Federated LearningOn Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental
The learning-augmented multi-option ski rental problem generalizes the classical ski rental problem in two ways: the algorithm is provided with a prediction on the number of days we can ski, and the ski rental options no…
Reinforcement Learning for Control Systems with Time Delays: A Comprehensive Survey
In the last decade, Reinforcement Learning (RL) has achieved remarkable success in the control and decision-making of complex dynamical systems. However, most RL algorithms rely on the Markov Decision Process assumption,…
Reinforcement LearningOnline Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health
Motivated by applications in digital health, this work studies the novel problem of online uniform sampling (OUS), where the goal is to distribute a sampling budget uniformly across unknown decision times. In the OUS pro…