On the Power of Randomness versus Advice in Online Computation

The recently introduced model of

advice complexity

of online problems tries to achieve a fine-grained analysis of the hardness of online problems by asking how many bits of advice about the still unknown parts of the input an oracle has to provide for an online algorithm to guarantee a specific competitive ratio. Until now, only deterministic online algorithms with advice were considered in the literature. In this paper, we consider, for the first time, online algorithms having access to both random bits and advice bits. For this, we introduce the online problem (

n

,

k

)-

Boxes

: Given a number of

n

closed boxes, an adversary hides

$k<\sqrt{n}$

items, each of unit value, within

k

consecutive boxes. The goal is to open exactly

k

boxes and gain as many items as possible.

In the classical online setting without advice, we show that, if

k

(

k

 + 1) ≤ 

n

, any deterministic algorithm is not competitive, because the adversary can ensure that not a single item is found. However, randomization drastically increases the gain in expectation. More precisely, we prove that the expected gain is in the order of

k

3

/

n

and show that this bound is tight up to some constant factor. A crucial result of our analysis is the proof of the existence of two thresholds for the amount of random bits used for solving (

n

,

k

)-

Boxes

. If the amount of random bits is below the first threshold, randomization does not help at all. If, on the other hand, the amount of randomness is above the second threshold of about log

n

 − 2log

k

random bits, then any additional random bit does not help to improve the gain.

As our main result, we analyze the advice complexity of the boxes problem both for deterministic and randomized online algorithms and give a tight trade-off between the number of random bits and advice bits needed for achieving a specific competitive ratio.