Minimizing a Combinatorial Function
Authors:
- Ding Zhu DuDDDing Zhu Du
- F. K. HwangFHF. K. Hwang
- 1 December 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 3 (4) , 523-528
Abstract
Let $M( N,d )$ denote the minimax number of group tests required for the identification of the d defectives in a set of N items. It is of interest to determine the values of N and d for which $M ( N,d ) = N - 1$ (achieved by testing the first $N - 1$ items one by one). Recently it has been proved that $M ( N,d ) = N - 1$ for $N < \lfloor 2.5 d \rfloor $. A lemma crucially used to obtain that result is the following: \[M ( N,d )\geqq \min \left\{ N - 1,2 t + \left\lceil \log_2 \begin{pmatrix} N - t \\ d - t \end{pmatrix} \right\rceil \right\}. \] The problem is to find a suitable t such that \[N - 1\leqq 2t + \left\lceil \log _2 \begin{pmatrix} N - t \\ d - t \end{pmatrix} \right\rceil \] and $d/N$ is minimized. However, standard methods do not work for this minimization problem. In this paper we propose a novel method to solve the minimization problem to obtain the new result: $M ( N,d ) = N - 1$ for $N\leqq \lfloor 2.625d \rfloor $.
Keywords
This publication has 1 reference indexed in Scilit:
- A Boundary Problem for Group TestingSIAM Journal on Algebraic Discrete Methods, 1981