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|script T sign|-approximable (where script T sign denotes the collection of sets to be covered) and it cannot be approximated within a factor smaller than log |script T sign|, 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.
OPTIMAL COVERING DESIGNS: COMPLEXITY RESULTS AND NEW BOUNDS / P. CRESCENZI; G. ROSSI; F. MONTECALVO. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 144:(2004), pp. 281-290. [10.1016/j.dam.2003.11.006]
OPTIMAL COVERING DESIGNS: COMPLEXITY RESULTS AND NEW BOUNDS
CRESCENZI, PIERLUIGI;
2004
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|script T sign|-approximable (where script T sign denotes the collection of sets to be covered) and it cannot be approximated within a factor smaller than log |script T sign|, 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.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
