Superselectors: efficient constructions and applications
From MaRDI portal
Publication:3586463
DOI10.1007/978-3-642-15775-2_18zbMATH Open1287.68143arXiv1010.1024OpenAlexW2963449712MaRDI QIDQ3586463FDOQ3586463
Authors: Ferdinando Cicalese, Ugo Vaccaro 
Publication date: 6 September 2010
Published in: Algorithms – ESA 2010 (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1010.1024
Recommendations
- Low-weight superimposed codes and their applications
- Low-weight superimposed codes and related combinatorial structures: bounds and applications
- Fundamentals of Computation Theory
- scientific article; zbMATH DE number 1947404
- Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels.
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)
