Optimal covering designs: complexity results and new bounds

In this paper we investigate the problem of computing optimal lottery schemes. From a computational complexity point of view, we prove that the variation of this problem in which the sets to be covered are specified in the input is log \T \-approximable (where denotes the collection of sets to be covered) and it cannot be approximated within a factor smaller than log \T\, unless P = Np. From a combinatorial point of view, we propose new constructions based on the combination of the partitioning technique and of known results regarding the construction of sets of coverings. By means of this combination we will be able to improve several upper bounds on the cardinality of optimal lottery schemes. (C) 2004 Elsevier B.V. All rights reserved.