Online Variable Sized Covering

AbstractWe consider one-dimensional and multidimensional vector covering with variable sized bins. In the one-dimensional case, we consider variable sized bin covering with bounded item sizes. For every finite set of bins B, and upper bound 1/m on the size of items for some integer m, we define a ratio r(B, m). We prove this is the best possible competitive ratio for the set of bins B and the parameter m by giving both an algorithm with competitive ratio r(B, m) and an upper bound of r(B, m) on the competitive ratio of any online deterministic or randomized algorithm. The ratio satisfies r(B, m)≥m/(m+1) and equals this number if all bins are of size 1. For multidimensional vector covering we consider the case where each bin is a binary d-dimensional vector. It was shown by N. Alon, Y. Azar, J. Csirik, L. Epstein, S. V. Sevastianov, A. P. A. Vestjens, and G. J. Woeginger (1998, Algorithmica 21, 104–118) that if B contains a single bin which is all 1, then the best competitive ratio is Θ(1/d). We show an upper bound of 1/2d(1−o(1)) for the general problem, and consider four special case variants. We show an algorithm with optimal competitive ratio 1/2 for the model where each bin in B is a standard basis vector. We consider the model where B consists of all unit prefix vectors. A unit prefix vector has i leftmost components of 1, and all other components are 0. We show that this model is harder than the case of standard basis vector bins by giving an upper bound of O(1/log d) on the competitive ratio of any deterministic or randomized algorithm. Next, we discuss the model where B contains all binary vectors. We show this model is easier than the model of one bin type which is all 1 by giving an algorithm with competitive ratio Ω(1/log d). The most interesting multidimensional case is d=2. The results of N. Alon et al. give a 0.25-competitive algorithm for B={(1, 1)} and an upper bound of 0.4 on the competitive ratio of any algorithm. In this paper we consider all other models for d=2. For standard basis vectors, we give an algorithm with optimal competitive ratio 1/2. For unit prefix vectors we give an upper bound of 4/9 on the competitive ratio of any deterministic or randomized algorithm. For the model where B consists of all binary vectors, we design an algorithm with ratio larger than 0.4. These results show that all above relations between models hold for d=2 as well