<p>In the context of fault-detection problems, the objective is to identify all defective items among a set of <i>n</i> binary-state items using the minimum number of tests. The group testing paradigm, which allows testing a subset of items in a single test, serves as a fundamental technique for efficiently classifying large populations. We study a central problem in the combinatorial group testing model where the number <i>d</i> of defective items is unknown in advance. Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(M_\alpha (d|n)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>M</mi> <mi>α</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo stretchy="false">|</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denote the maximum number of tests required by an algorithm <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> for this problem, and <i>M</i>(<i>d</i>,&#xa0;<i>n</i>) denote the minimum number of tests required in the worst case when <i>d</i> is known in advance. An algorithm <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\alpha \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>α</mi> </math></EquationSource> </InlineEquation> is called a <i>c</i>-<i>competitive algorithm</i> if there exist constants <i>c</i> and <i>a</i> such that, for <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(0\le d &lt; n\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>d</mi> <mo>&lt;</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(M_{\alpha }(d|n)\le cM(d,n)+a\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>M</mi> <mi>α</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo stretchy="false">|</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mi>c</mi> <mi>M</mi> <mrow> <mo stretchy="false">(</mo> <mi>d</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> <mo>+</mo> <mi>a</mi> </mrow> </math></EquationSource> </InlineEquation>. We develop a <i>modular two-stage framework</i> for this problem: (i) a constant-size preliminary-testing stage that extracts coarse information about <i>d</i>; and (ii) a conditional invocation stage that, based on the preliminary outcome, invokes either our newly developed <i>up-zig-zag</i> approach or an existing strongly competitive algorithm. With carefully designed switching rules, this framework yields a deterministic adaptive algorithm with a competitive ratio <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(c \le 1.431\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo>≤</mo> <mn>1.431</mn> </mrow> </math></EquationSource> </InlineEquation>, improving the previous best-known bound of 1.452. This guarantee is achieved via a reusable integration principle that combines a constant preliminary overhead with a second-stage choice tailored to the remaining uncertainty.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A new adaptive algorithm for competitive group testing

  • Jun Wu,
  • Yongxi Cheng,
  • Zhen Yang,
  • Feng Chu,
  • Junkai He

摘要

In the context of fault-detection problems, the objective is to identify all defective items among a set of n binary-state items using the minimum number of tests. The group testing paradigm, which allows testing a subset of items in a single test, serves as a fundamental technique for efficiently classifying large populations. We study a central problem in the combinatorial group testing model where the number d of defective items is unknown in advance. Let \(M_\alpha (d|n)\) M α ( d | n ) denote the maximum number of tests required by an algorithm \(\alpha \) α for this problem, and M(dn) denote the minimum number of tests required in the worst case when d is known in advance. An algorithm \(\alpha \) α is called a c-competitive algorithm if there exist constants c and a such that, for \(0\le d < n\) 0 d < n , \(M_{\alpha }(d|n)\le cM(d,n)+a\) M α ( d | n ) c M ( d , n ) + a . We develop a modular two-stage framework for this problem: (i) a constant-size preliminary-testing stage that extracts coarse information about d; and (ii) a conditional invocation stage that, based on the preliminary outcome, invokes either our newly developed up-zig-zag approach or an existing strongly competitive algorithm. With carefully designed switching rules, this framework yields a deterministic adaptive algorithm with a competitive ratio \(c \le 1.431\) c 1.431 , improving the previous best-known bound of 1.452. This guarantee is achieved via a reusable integration principle that combines a constant preliminary overhead with a second-stage choice tailored to the remaining uncertainty.