The minimum likely column cover problem |
| |
| Authors: | Pilu Crescenzi |
| |
| Affiliation: | a Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Via C. Lombroso 6/17, 50134 Firenze, Italy
b Dipartimento di Matematica Ulisse Dini, Università degli Studi di Firenze, Viale Morgagni 67a, 50134 Firenze, Italy |
| |
| Abstract: | In this paper we introduce and study the problem of computing optimal lottery schemes in the case in which a weight function is specified over the domain set. In particular, we prove that if the number of required hits is equal to 1, then the problem is solvable in polynomial time, and that if the number of required hits is equal to t, then the problem admits a polynomial-time  -approximation algorithm, where k denotes the size of the tuples to be hit. |
| |
| Keywords: | Approximation algorithms Combinatorial problems Computational complexity Covering design Lottery schema |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
