The problem of computing optimal lottery schemes in the case in which a weight function was specified over the domain set was discussed. It was proved that if the number of required hits was equal to 1, then the problem was solvable in polynomial time. A problem where k and t were two natural numbers and represent what really happens when some decides to play TOTOGOL was presented. It was found that when the number of hits was equal to t, then the problem admitted a polynomial-time (tk)-approximation algorithm where k denotes the size of the tuples to be hit.
THE MINIMUM LIKELY COLUMN COVER PROBLEM / P. CRESCENZI; F. GRECO. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - STAMPA. - 89:(2004), pp. 175-179. [10.1016/j.ipl.2003.11.003]
THE MINIMUM LIKELY COLUMN COVER PROBLEM
CRESCENZI, PIERLUIGI;
2004
Abstract
The problem of computing optimal lottery schemes in the case in which a weight function was specified over the domain set was discussed. It was proved that if the number of required hits was equal to 1, then the problem was solvable in polynomial time. A problem where k and t were two natural numbers and represent what really happens when some decides to play TOTOGOL was presented. It was found that when the number of hits was equal to t, then the problem admitted a polynomial-time (tk)-approximation algorithm where k denotes the size of the tuples to be hit.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
