Optimal Detection of Two Defectives with a Parity Check Device
X. M. Chang, F. K. Hwang, Jia Feng Weng · SIAM Journal on Discrete Mathematics · 1988
Recently the problems of detecting two defectives under various testing models have been studied as a forum for exploring the boundaries between easy problems and hard problems in combinatorial searching. In this paper five levels of optimality to measure the difficulty are defined. These five levels are minimax, almost surely minimax, measure p minimax, first-order minimax, and order-of-magnitude minimax. A new procedure is given, which is almost surely minimax for the parity check model, improving the previously best procedure which is measure p minimax.