Minimizing a Combinatorial Function

Authors:
  • DDDing Zhu Du
    Ding Zhu Du
  • FHF. K. Hwang
    F. K. Hwang

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 $.

This publication has 1 reference indexed in Scilit: