Permutation predictions for non-clairvoyant scheduling
A Lindermayr, N Megow - Proceedings of the 34th ACM Symposium on …, 2022 - dl.acm.org
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a
priori unknown processing requirements with the objective to minimize the total (weighted) …
priori unknown processing requirements with the objective to minimize the total (weighted) …
Paging with succinct predictions
A Antoniadis, J Boyar, M Eliás… - International …, 2023 - proceedings.mlr.press
Paging is a prototypical problem in the area of online algorithms. It has also played a central
role in the development of learning-augmented algorithms. Previous work on learning …
role in the development of learning-augmented algorithms. Previous work on learning …
Learning-augmented query policies for minimum spanning tree with uncertainty
We study how to utilize (possibly erroneous) predictions in a model for computing under
uncertainty in which an algorithm can query unknown data. Our aim is to minimize the …
uncertainty in which an algorithm can query unknown data. Our aim is to minimize the …
A universal error measure for input predictions applied to online graph problems
G Bernardini, A Lindermayr… - Advances in …, 2022 - proceedings.neurips.cc
We introduce a novel measure for quantifying the error in input predictions. The error is
based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a …
based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a …
Contract scheduling with predictions
S Angelopoulos, S Kamali - Journal of Artificial Intelligence Research, 2023 - jair.org
Contract scheduling is a general technique that allows the design of systems with
interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous …
interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous …
Minimalistic predictions to schedule jobs with online precedence constraints
We consider non-clairvoyant scheduling with online precedence constraints, where an
algorithm is oblivious to any job dependencies and learns about a job only if all of its …
algorithm is oblivious to any job dependencies and learns about a job only if all of its …
Learning-augmented online TSP on rings, trees, flowers and (almost) everywhere else
We study the Online Traveling Salesperson Problem (OLTSP) with predictions. In OLTSP, a
sequence of initially unknown requests arrive over time at points (locations) of a metric …
sequence of initially unknown requests arrive over time at points (locations) of a metric …
Online interval scheduling with predictions
In online interval scheduling, the input is an online sequence of intervals, and the goal is to
accept a maximum number of non-overlapping intervals. In the more general disjoint path …
accept a maximum number of non-overlapping intervals. In the more general disjoint path …
Exploration of graphs with excluded minors
J Baligács, Y Disser, I Heinrich… - arXiv preprint arXiv …, 2023 - arxiv.org
We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs
(1994) and prove a constant competitive ratio on minor-free graphs. This result …
(1994) and prove a constant competitive ratio on minor-free graphs. This result …
Learning-Based Algorithms for Graph Searching Problems
We consider the problem of graph searching with prediction recently introduced by Banerjee
et al.(2023). In this problem, an agent starting at some vertex r has to traverse a (potentially …
et al.(2023). In this problem, an agent starting at some vertex r has to traverse a (potentially …