Related papers: Learning-Augmented Algorithms for Online Steiner Tree

Learning-Augmented Algorithms for Online Steiner Tree

URL: http://arxiv.org/abs/2112.05353v2
Date: Sat, 18 Mar 2023 12:33:03 GMT
Title: Learning-Augmented Algorithms for Online Steiner Tree
Authors: Chenyang Xu and Benjamin Moseley
Abstract summary: This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. We show that the new online algorithms have strong performance even with modestly correct predictions.
Score: 14.506230077020994
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm's worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms' performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.

Related papers

Improving Online Algorithms via ML Predictions [19.03466073202238]
We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.
arXiv Detail & Related papers (2024-07-25T02:17:53Z)
Competitive Algorithms for Online Knapsack with Succinct Predictions [16.793099279933163]
In the online knapsack problem, the goal is to pack items arriving online with different values and weights into a capacity-limited knapsack to maximize the total value of the accepted items. We study textitlearning-augmented algorithms for this problem, which aim to use machine-learned predictions to move beyond pessimistic worst-case guarantees.
arXiv Detail & Related papers (2024-06-26T20:38:00Z)
Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
We consider non-clairvoyant scheduling with online precedence constraints. An algorithm is oblivious to any job dependencies and learns about a job only if all of its predecessors have been completed.
arXiv Detail & Related papers (2023-01-30T13:17:15Z)
A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
arXiv Detail & Related papers (2022-05-25T15:24:03Z)
Online Algorithms with Multiple Predictions [17.803569868141647]
This paper studies online algorithms augmented with multiple machine-learned predictions. Our algorithm incorporates the use of predictions in the classic potential-based analysis of online algorithms.
arXiv Detail & Related papers (2022-05-08T17:33:01Z)
Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
arXiv Detail & Related papers (2022-02-21T13:18:11Z)
Robustification of Online Graph Exploration Methods [59.50307752165016]
We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
arXiv Detail & Related papers (2021-12-10T10:02:31Z)
Double Coverage with Machine-Learned Advice [100.23487145400833]
We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
arXiv Detail & Related papers (2021-03-02T11:04:33Z)
Online Paging with a Vanishing Regret [6.520803851931362]
This paper considers a variant of the online paging problem, where the online algorithm has access to multiple predictors, each producing a sequence of predictions for the page arrival times. The predictors may have occasional prediction errors and it is assumed that at least one of them makes a sublinear number of prediction errors in total. Our main result states that this assumption suffices for the design of a randomized online algorithm whose time-average regret with respect to the optimal offline algorithm tends to zero as the time tends to infinity.
arXiv Detail & Related papers (2020-11-18T18:17:49Z)
Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust. We provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions.
arXiv Detail & Related papers (2020-10-22T04:51:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.