The advice model of online computation captures the setting in which the online algorithm is
given some information concerning the request sequence. This paradigm allows to establish …

Bin packing is a classic optimization problem with a wide range of applications, from load
balancing to supply chain management. In this work, we study the online variant of the …

Contract scheduling is a general technique that allows the design of systems with
interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous …

We introduce the study of search problems, in a setting in which the searcher has some
information, or hint concerning the hiding target. In particular, we focus on one of the …

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 …

A variant of the online knapsack problem is considered in the settings of trusted and
untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find …

A variant of the online knapsack problem is considered in the setting of predictions. In Unit
Profit Knapsack, the items have unit profit, ie, the goal is to pack as many items as possible …

We study a generalization of the advice complexity model of online computation in which the
advice is provided by an untrusted source. Our objective is to quantify the impact of …

ALG (𝐼). It is obvious that a competitive ratio closer to 1 is better. For the online conversion
problem under unknown horizon, it has been shown that the best possible competitive ratio …

We study the nascent setting of online computation with imperfect advice, in which the online
algorithm is enhanced by some prediction encoded in the form of a possibly erroneous …