We describe algorithms which are guaranteed to find a covering on-line provided that the total volume (the sum of sid) is at least 2d+3. (The true bound is actually a little smaller.) This performance guarantee is quite strong, considering that the existence of an (off-line) covering can only be ensured if the total volume is at least 2d-1. The best previous on-line bound was 4d, due to Wlodek Kuperberg.
We reduce this problem to an online interval covering problem for q-adic
intervals. In this problem, we have to cover the unit interval [0,1] by
intervals whose sizes are negative powers of q. The endpoints of
an interval of side length q-k are restricted
to fall on multiples of q-k. For this class of
problems, we consider a kind of simple on-line algorithm, the so-called
"method of the n-th segment", for some integer n>1. We give
performance guarantees for these algorithms, and show that the cases n=q+1,
n=q+2, and n=q+1 give the best results, depending
on q. For q=2d these methods carry over
to the covering problem for d-dimensional cubes whose side lengths
are powers of 2.