Combinatorial group testing and its applications

✍ Scribed by Du D.-Z., Hwang F.K.

• Publisher: WS
• Year: 2000
• Tongue: English
• Leaves: 336
• Series: Applied Mathematics
• Edition: 2ed
• Category: Library

✦ Synopsis

Group testing has been used in medical, chemical and electrical testing, coding, drug screening, pollution control, multiaccess channel management, and more recently in data verification, clone library screening and AIDS testing. The mathematical model can be either combinatorial or probabilistic. This work is a summary of all important results under the combinatorial model, and it demonstrates their applications in real problems. Some other search problems, including the famous counterfeit-coins problem, are also studied in depth. This second edition is updated and embraces the growing importance of two topics: nonadaptive algorithms and error tolerance. Two new chapters, one on clone library screening and the other on error tolerance, have been added. Also included is a new chapter on counterfeit coins, and the chapters have been reorganized into parts to provide focuses and perspectives.

✦ Table of Contents

Contents......Page 10
Preface......Page 6
Preface to the Second Edition......Page 8
1.1 The History of Group Testing......Page 14
1.2 A Prototype Problem and Some General Remarks......Page 18
1.3 Some Practical Considerations......Page 20
References......Page 22
Part I Sequential Group Testing Algorithms......Page 24
2.1 The Binary Tree Representation of a Sequential Algorithm......Page 26
2.2 The Structure of Group Testing......Page 33
2.3 Li's s-Stage Algorithm......Page 36
2.4 Hwang's Generalized Binary Splitting Algorithm......Page 37
2.5 The Nested Class......Page 40
2.6 (d, n) Algorithms and Merging Algorithms......Page 45
2.7 Number of Group Testing Algorithms......Page 48
References......Page 50
3.1 Two Disjoint Sets Each Containing Exactly One Defective......Page 52
3.2 An Application to Locating Electrical Shorts......Page 57
3.3 The 2-Defective Case......Page 62
3.4 The 3-Defective Case......Page 67
3.5 When is Individual Testing Minimax?......Page 70
3.6 Identifying a Single Defective with Parallel Tests......Page 73
References......Page 75
4.1 The First Competitiveness......Page 78
4.2 Bisecting......Page 80
4.3 Doubling......Page 84
4.4 Jumping......Page 86
4.5 The Second Competitiveness......Page 90
4.6 Digging......Page 93
4.7 Tight Bound......Page 95
References......Page 100
5.1 Ulam's Problem......Page 102
5.2 General Lower and Upper Bounds......Page 108
5.3 Linearly Bounded Lies (1)......Page 113
5.4 The Chip Game......Page 117
5.5 Linearly Bounded Lies (2)......Page 122
5.6 Other Restrictions on Lies......Page 125
References......Page 128
6.1 General Notions......Page 130
6.2 The Prototype Group Testing Problem is in PSPACE......Page 132
6.3 Consistency......Page 133
6.4 Determinacy......Page 135
6.5 On Sample Space S(n)......Page 136
6.6 Learning by Examples......Page 142
References......Page 143
Part II Nonadaptive Group Testing Algorithms......Page 144
7.1 The Matrix Representation......Page 146
7.2 Basic Relations and Bounds......Page 147
7.3 Constant Weight Matrices......Page 153
7.4 General Constructions......Page 158
7.5 The Small d Cases......Page 164
References......Page 172
8.1 Random Matrices......Page 176
8.2 Macula's Error Tolerance d-Disjunct Matrices......Page 180
8.3 q-Error-Tolerance d-Disjunct Matrices......Page 183
References......Page 188
9.1 Clone Library Screening......Page 190
9.2 Deterministic Designs......Page 193
9.3 Random Designs......Page 196
9.4 Some Additional Problems......Page 201
References......Page 205
Part III Extended Group Testing Models......Page 208
10 Multiaccess Channels and Extensions......Page 210
10.1 Multiaccess Channels......Page 211
10.2 Nonadaptive Algorithms......Page 215
10.3 Two Variations......Page 218
10.4 The k-Channel......Page 221
References......Page 224
11.1 Symmetric Group Testing......Page 226
11.2 Some Additive Models......Page 228
11.3 A Maximum Model......Page 234
11.4 Some Models for d = 2......Page 237
References......Page 243
12.1 2-Optimal Graphs......Page 246
12.2 Solution of the Du-Hwang Conjecture......Page 249
12.3 Defective Vertices......Page 255
12.4 On Trees......Page 258
References......Page 263
Part IV Other Related Searching Problems......Page 266
13.1 Midpoint Strategy......Page 268
13.2 Fibonacci Search......Page 270
13.3 Minimum Root Identification......Page 274
References......Page 281
14.1 Introduction......Page 284
14.2 Bentley-Yao Algorithms......Page 286
14.3 Search with Lies......Page 290
14.4 Unbounded Fibonacci Search......Page 292
References......Page 293
15.1 Examples......Page 294
15.2 Polyhedral Membership......Page 296
15.3 Boolean Formulas and Decision Trees......Page 298
15.4 Recognition of Graph Properties......Page 302
References......Page 305
16.1 One Counterfeit Coin......Page 308
16.2 Two, Three, and More Counterfeit Coins......Page 314
16.3 The All-Equal Problem......Page 315
16.4 Anti-Hadamard Matrices......Page 321
16.5 Coins with Arbitrary Weights......Page 327
References......Page 328
Index......Page 332