On-line algorithms for the q-adic covering of the unit interval and for covering a cube by cubes
On-line algorithms for the \(q\)-adic covering of the unit interval and for covering a cube by cubes
An algorithm for the on-line \(q\)-adic covering of the unit interval by sequences of segments is presented. This algorithm guarantees covering provided the total length of segments is at least \(1+\frac{2}{q}-\frac{1}{q^3}\). Next a more sophisticated algorithm is proposed which lowers the above estimate to \(1+\frac{5}{3}\cdot\frac{1}{q}+\frac{5}{3}\cdot\frac{1}{q^2}\). As a consequence, every sequence of cubes of sides at most 1 in \(E^d\) whose total volume is at least \(2^d+\frac{5}{3} + \frac{5}{3}\cdot 2^{-d}\) permits an on-line covering of the unit cube in \(E^d\).
- On-line q-adic covering by the method of the n-th segment and its application to on-line covering by cubes
- Efficient on-line algorithm for maintaining k-cover of sparse bit-strings
- scientific article; zbMATH DE number 3557813 (Why is no real title available?)
- scientific article; zbMATH DE number 2065240 (Why is no real title available?)
This page was built for publication: On-line algorithms for the \(q\)-adic covering of the unit interval and for covering a cube by cubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1856599)
