TY - JOUR
T1 - D-Disjunct matrices
T2 - Bounds and Lovâsz Local Lemma
AU - Yeh, Hong Gwa
N1 - Funding Information:
Supported in part by the National Science Council under grant NSC 89-2115-M-390-002. E-mail address: [email protected] (H.-G. Yeh).
PY - 2002/6/6
Y1 - 2002/6/6
N2 - A binary matrix is said to be d-disjunct if the union (or Boolean sum) of any d columns does not contain any other column. Such matrices constitute a basis for nonadaptive group testing algorithms and binary (/-superimposed codes. Let t(d,n) denote the minimum number of rows for a (/-disjunct matrix with n columns. In this note we study the bounds of t(d,n) and its variations. Lovdsz Local Lemma (Colloq. Math. Soc. Jànos Bolyai 10 (1974) 609-627; The Probabilistic Method, Wiley, New York, 1992 (2nd Edition, 2000)) and other probabilistic methods are used to extract better bounds. For a given random t × n binary matrix, the Stein-Chen method is used to measure how 'bad' it is from a (d-disjunct matrix.
AB - A binary matrix is said to be d-disjunct if the union (or Boolean sum) of any d columns does not contain any other column. Such matrices constitute a basis for nonadaptive group testing algorithms and binary (/-superimposed codes. Let t(d,n) denote the minimum number of rows for a (/-disjunct matrix with n columns. In this note we study the bounds of t(d,n) and its variations. Lovdsz Local Lemma (Colloq. Math. Soc. Jànos Bolyai 10 (1974) 609-627; The Probabilistic Method, Wiley, New York, 1992 (2nd Edition, 2000)) and other probabilistic methods are used to extract better bounds. For a given random t × n binary matrix, the Stein-Chen method is used to measure how 'bad' it is from a (d-disjunct matrix.
KW - D-disjunct matrix
KW - Group testing
KW - Lovâsz local lemma
KW - Probabilistic method
KW - Stein-Chen approximation theorem
UR - http://www.scopus.com/inward/record.url?scp=31244434340&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(01)00452-6
DO - 10.1016/S0012-365X(01)00452-6
M3 - 期刊論文
AN - SCOPUS:31244434340
SN - 0012-365X
VL - 253
SP - 97
EP - 107
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1-3
ER -