Superselectors: efficient constructions and applications

DOI10.1007/978-3-642-15775-2_18MaRDI QIDQ3586463zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Ugo Vaccaro

Publication date 6 September 2010

Published in Algorithms – ESA 2010 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.1024

Combinatorics in computer science (68R05) Nonnumerical algorithms (68W05)

Abstract: We introduce a new combinatorial structure: the superselector. 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, (d,ell)-list-disjunct matrices, MUT_k(r)-families, FUT(k, a)-families, 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.

Recommendations

Cited in

(2)

This page was built for publication: Superselectors: efficient constructions and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586463)