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 |\mathcal{T}|$-approximable (where $\mathcal{T}$ denotes the collection of sets to be covered) and it cannot be approximated within a factor smaller than $\log |\mathcal{T}|$, unless $\DP=\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