Combinatorial Group Testing and Its Applications

by Du, Ding-Zhu; Hwang, Frank K.

• ISBN13: 9789810241070
• ISBN10: 9810241070
• Edition: 2nd
• Format: Hardcover
• Copyright: 2000-05-01
• Publisher: WORLD SCIENTIFIC PUB CO INC

Summary

Group testing has been used in medical, chemical and electrical testing, coding, drug screening, pollution control, multiaccess channel management, and recently in data verification, clone library screening and AIDS testing. The mathematical model can be either combinatorial or probabilistic. This book summarizes all important results under the combinatorial model, and demonstrates their applications in real problems. Some other search problems, including the famous counterfeit-coins problem, are also studied in depth.

There are two reasons for publishing a second edition of this book. The first is the usual need to update the text (after six years) and correct errors. The second -- and more important -- reason is to accommodate the recent sudden growth of interest in applying the idea of group testing to clone library screening. This development is much more than just a new application, since the new application brings with it new objectives which require a new twist of theory. It also embraces the growing importance of two topics: nonadaptive algorithms and

Table of Contents

Preface	v
Preface to the Second Edition	vii
Introduction	1	(10)
The History of Group Testing	1	(4)
A Prototype Problem and Some General Remarks	5	(2)
Some Practical Considerations	7	(4)
References	9	(2)
Part I Sequential Group Testing Algorithms	11	(120)
General Sequential Algorithms	13	(26)
The Binary Tree Representation of a Sequential Algorithm	13	(7)
The Structure of Group Testing	20	(3)
Li's s-Stage Algorithm	23	(1)
Hwang's Generalized Binary Splitting Algorithm	24	(3)
The Nested Class	27	(5)
(d, n) Algorithms and Merging Algorithms	32	(3)
Number of Group Testing Algorithms	35	(4)
References	37	(2)
Sequential Algorithms for Special Cases	39	(26)
Two Disjoint Sets Each Containing Exactly One Defective	39	(5)
An Application to Locating Electrical Shorts	44	(5)
The 2-Defective Case	49	(5)
The 3-Defective Case	54	(3)
When is Individual Testing Minimax?	57	(3)
Identifying a Single Defective with Parallel Tests	60	(5)
References	62	(3)
Competitive Group Testing	65	(24)
The First Competitiveness	65	(2)
Bisecting	67	(4)
Doubling	71	(2)
Jumping	73	(4)
The Second Competitiveness	77	(3)
Digging	80	(2)
Tight Bound	82	(7)
References	87	(2)
Unreliable Tests	89	(28)
Ulam's Problem	89	(6)
General Lower and Upper Bounds	95	(5)
Linearly Bounded Lies (1)	100	(4)
The Chip Game	104	(5)
Linearly Bounded Lies (2)	109	(3)
Other Restrictions on Lies	112	(5)
References	115	(2)
Complexity Issues	117	(14)
General Notions	117	(2)
The Prototype Group Testing Problem is in PSPACE	119	(1)
Consistency	120	(2)
Determinacy	122	(1)
On Sample Space S(n)	123	(6)
Learning by Examples	129	(2)
References	130	(1)
Part II. Nonadaptive Group Testing Algorithms	131	(64)
Deterministic Designs and Superimposed Codes	133	(30)
The Matrix Representation	133	(1)
Basic Relations and Bounds	134	(6)
Constant Weight Matrices	140	(5)
General Constructions	145	(6)
The Small d Cases	151	(12)
References	159	(4)
Random Designs and Error Tolerance	163	(14)
Random Matrices	163	(4)
Macula's Error Tolerance d-Disjunct Matrices	167	(3)
q-Error-Tolerance d-Disjunct Matrices	170	(7)
References	175	(2)
DNA Applications	177	(18)
Clone Library Screening	177	(3)
Deterministic Designs	180	(3)
Random Designs	183	(5)
Some Additional Problems	188	(7)
References	192	(3)
Part III. Extended Group Testing Models	195	(58)
Multiaccess Channels and Extensions	197	(16)
Multiaccess Channels	198	(4)
Nonadaptive Algorithms	202	(3)
Two Variations	205	(3)
The k-Channel	208	(3)
Quantitative Channels	211	(2)
References	211	(2)
Additive Model and Others	213	(20)
Symmetric Group Testing	213	(2)
Some Additive Models	215	(6)
A Maximum Model	221	(3)
Some Models for d = 2	224	(9)
References	230	(3)
Group Testing on Graphs	233	(20)
2-Optimal Graphs	233	(3)
Solution of the Du-Hwang Conjecture	236	(6)
Defective Vertices	242	(3)
On Trees	245	(5)
Other Constraints	250	(3)
References	250	(3)
Part IV. Other Related Searching Problems	253	(66)
Optimal Search in One Variable	255	(16)
Midpoint Strategy	255	(2)
Fibonacci Search	257	(4)
Minimum Root Identification	261	(10)
References	268	(3)
Unbounded Search	271	(10)
Introduction	271	(2)
Bentley-Yao Algorithms	273	(4)
Search with Lies	277	(2)
Unbounded Fibonacci Search	279	(2)
References	280	(1)
Membership Problems	281	(14)
Examples	281	(2)
Polyhedral Membership	283	(2)
Boolean Formulas and Decision Trees	285	(4)
Recognition of Graph Properties	289	(6)
References	292	(3)
Counterfeit Coins	295	(24)
One Counterfeit Coin	295	(6)
Two, Three, and More Counterfeit Coins	301	(1)
The All-Equal Problem	302	(6)
Anti-Hadamard Matrices	308	(6)
Coins with Arbitrary Weights	314	(5)
References	315	(4)
Index	319