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.
Crescenzi, P., Montecalvo, F., Rossi, G. (2004). Optimal covering designs: complexity results and new bounds. DISCRETE APPLIED MATHEMATICS, 144, 281-290 [10.1016/j.dam.2003.11.006].
Optimal covering designs: complexity results and new bounds
ROSSI, GIANLUCA
2004-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
