We introduce a new combinatorial structure: superselectors. We show that superselectors subsume several important combinatorial structures used in the past few years to solve problems in group testing, compressed sensing, multi-channel conflict resolution and data security. We prove close upper and lower bounds on the size of superselectors and we provide efficient algorithms for their constructions. Albeit our bounds are very general, when they are instantiated on the combinatorial structures that are particular cases of superselectors (e.g., (p,k,n)-selectors [15], (d,ℓ)-list-disjunct matrices [25], MUT k (r)-families [28], FUT(k, α)-families [2], etc.) they match the best known bounds in terms of size of the structures (the relevant parameter in the applications). For appropriate values of parameters, our results also provide the first efficient deterministic algorithms for the construction of such structures.
Superselectors: Efficient Constructions and Applications
Ferdinando Cicalese
;
2010-01-01
Abstract
We introduce a new combinatorial structure: superselectors. We show that superselectors subsume several important combinatorial structures used in the past few years to solve problems in group testing, compressed sensing, multi-channel conflict resolution and data security. We prove close upper and lower bounds on the size of superselectors and we provide efficient algorithms for their constructions. Albeit our bounds are very general, when they are instantiated on the combinatorial structures that are particular cases of superselectors (e.g., (p,k,n)-selectors [15], (d,ℓ)-list-disjunct matrices [25], MUT k (r)-families [28], FUT(k, α)-families [2], etc.) they match the best known bounds in terms of size of the structures (the relevant parameter in the applications). For appropriate values of parameters, our results also provide the first efficient deterministic algorithms for the construction of such structures.File | Dimensione | Formato | |
---|---|---|---|
ESA2010.pdf
solo utenti autorizzati
Tipologia:
Documento in Pre-print
Licenza:
Accesso ristretto
Dimensione
248 kB
Formato
Adobe PDF
|
248 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.