In online scenarios requests arrive over time, and each request must be serviced in an
irrevocable manner before the next request arrives. Online algorithms with advice is an area …

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 …

Online algorithms with advice is an area of research where one attempts to measure how
much knowledge of the future is necessary to achieve a given competitive ratio. The lower …

We study the advice complexity and the random bit complexity of the online knapsack
problem. Given a knapsack of unit capacity, and n items that arrive in successive time steps …

Competitive analysis is the established tool for measuring the output quality of algorithms
that work in an online environment. Recently, the model of advice complexity has been …

We consider the online bin packing problem under the advice complexity model where the
“online constraint” is relaxed and an algorithm receives partial information about the future …

We study the problem of exploring an unknown undirected graph with non-negative edge
weights. Starting at a distinguished initial vertex s, an agent must visit every vertex of the …

The advice complexity of an online problem describes the additional information both
necessary and sufficient for online algorithms to compute solutions of a certain quality. In this …

We consider the minimum spanning tree problem with predictions, using the weight-arrival
model, ie, the graph is given, together with predictions for the weights of all edges. Then the …

We provide simple but surprisingly useful direct product theorems for proving lower bounds
on online algorithms with a limited amount of advice about the future. As a consequence, we …