Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.09320 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912710868860928 |
|---|---|
| author | Wu, Jun Cheng, Yongxi Yang, Zhen Chu, Feng He, Junkai |
| author_facet | Wu, Jun Cheng, Yongxi Yang, Zhen Chu, Feng He, Junkai |
| contents | 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_α(d|n)$ denote the maximum number of tests required by an algorithm $α$ for this problem, and $M(d,n)$ denote the minimum number of tests required in the worst case when $d$ is known in advance. An algorithm $α$ is called a $c$-\emph{competitive algorithm} if there exist constants $c$ and $a$ such that, for $0\le d < n$, $M_α(d|n)\le cM(d,n)+a$. We design a new adaptive algorithm with a competitive constant $c \le 1.431$, thus pushing the competitive ratio below the best-known one of $1.452$. To achieve this, we propose a novel solution framework based on an unexplored up-zig-zag strategy and a studied strongly competitive algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09320 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A 1.431-Competitive Algorithm for Combinatorial Group Testing Wu, Jun Cheng, Yongxi Yang, Zhen Chu, Feng He, Junkai Combinatorics 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_α(d|n)$ denote the maximum number of tests required by an algorithm $α$ for this problem, and $M(d,n)$ denote the minimum number of tests required in the worst case when $d$ is known in advance. An algorithm $α$ is called a $c$-\emph{competitive algorithm} if there exist constants $c$ and $a$ such that, for $0\le d < n$, $M_α(d|n)\le cM(d,n)+a$. We design a new adaptive algorithm with a competitive constant $c \le 1.431$, thus pushing the competitive ratio below the best-known one of $1.452$. To achieve this, we propose a novel solution framework based on an unexplored up-zig-zag strategy and a studied strongly competitive algorithm. |
| title | A 1.431-Competitive Algorithm for Combinatorial Group Testing |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.09320 |