##
Marek Lassak, Janusz Januszewski, Günter Rote, and Gerhard Woeginger:

#
1. On-line q-adic covering by the method of the n-th segment and its application
to on-line covering by cubes

*Beiträge zur Algebra
und Geometrie - Contributions to Algebra and Geometry 37 (no. 1) (1996),
51-65, (Zbl 863.52010).*
###
Abstract

In the on-line covering problem for covering the unit cube by cubes, we
are given a sequence of smaller cubes of side lengths *s*_{1},
*s*_{2},...,*s*_{n}, and we have to place them
in such a way that the whole unit cube in *d*-dimensional Euclidean
space is covered if possible. The cubes are axis-parallel, they are allowed
to overlap, but the algorithm must place the *i*-th cube before knowing
the future cubes *s*_{i}_{+1}, *s*_{i}_{+2},...
We describe algorithms which are guaranteed to find a covering on-line
provided that the total volume (the sum of *s*_{i}^{d})
is at least 2^{d}+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 2^{d}-1. The best previous on-line bound
was 4^{d}, 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*=2^{d} these methods carry over
to the covering problem for *d*-dimensional cubes whose side lengths
are powers of 2.

#
2. Solution to problem 74

*Mathematische Semesterberichte 43 (1996), 94-100.*
###
Abstract

This paper contains a different proof of a special case of the main result
of the above paper, complemented by a lower-bound construction.