Smart elements in combinatorial group testing problems

DOI10.1007/S10878-018-0248-ZMaRDI QIDQ1752611zbMATH OpenOpenAlexFDO

Authors Dániel Gerbner, Máté Vizer

Publication date 24 May 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05398, http://real.mtak.hu/72833/7/smart-elements-combinatorial.pdf

zbMATH Keywords

information sharingcombinatorial group testingnon-adaptive

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: In combinatorial group testing problems Questioner needs to find a special element $xin[n]$ by testing subsets of $[n]$. Tapolcai et al. introduced a new model, where each element knows the answer for those queries that contain it and each element should be able to identify the special one. Using classical results of extremal set theory we prove that if $mathcal{F}_{n}subset{2}^{[n]}$ solves the non-adaptive version of this problem and has minimal cardinality, then ${\displaystyle }$lim_{n ightarrow infty} frac{|mathcal{F}_n|}{log_2 n} = log_{(3/2)}2.${\displaystyle }$ This improves results by Tapolcai et al. We also consider related models inspired by secret sharing models, where the elements should share information among them to find out the special one. Finally the adaptive versions of the different models are investigated.

Recommendations

• Smart elements in combinatorial group testing problems with more defectives
• scientific article; zbMATH DE number 823957
• scientific article; zbMATH DE number 6530141
• An efficient algorithm for combinatorial group testing
• scientific article; zbMATH DE number 1508646
• Sparse Combinatorial Group Testing
• Improved Combinatorial Group Testing Algorithms for Real‐World Problem Sizes
• Algorithms and Data Structures
• New combinatorial designs and their applications to group testing
• Combinatorial group testing in bipartite graphs

Cites work

• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• scientific article; zbMATH DE number 844156 (Why is no real title available?)
• scientific article; zbMATH DE number 3392464 (Why is no real title available?)
• A note on tilted Sperner families with patterns
• Combinatorial pair testing: distinguishing workers from slackers
• Density-based group testing
• Group Testing With Probabilistic Tests: Theory, Design and Application
• Minimal completely separating systems
• New rate pairs in the zero-error capacity region of the binary multiplying channel without feedback
• ON THE CONSTRUCTION OF BALANCED INCOMPLETE BLOCK DESIGNS
• On a problem concerning separating systems of a finite set
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Secret-Sharing Schemes: A Survey
• Smart elements in combinatorial group testing problems with more defectives
• Some Remarks on the Triple Systems of Steiner.
• Threshold Group Testing
• Two new perspectives on multi-stage group testing
• Union-free hypergraphs and probability theory

Cited in

(2)

• Smart elements in combinatorial group testing problems with more defectives
• Majority problems of large query size

This page was built for publication: Smart elements in combinatorial group testing problems

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