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).


In the on-line covering problem for covering the unit cube by cubes, we are given a sequence of smaller cubes of side lengths s1, s2,...,sn, 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 si+1, si+2,...

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.

  PostScript file (gzippedpdf file  TeX .dvi file (gzipped)

2. Solution to problem 74

Mathematische Semesterberichte 43 (1996), 94-100.


This paper contains a different proof of a special case of the main result of the above paper, complemented by a lower-bound construction.
  PostScript file (gzippedpdf file
other papers about this subject