An Efficient Algorithm for Group Testing with Runlength Constraints
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914939622391808 |
|---|---|
| author | Dalai, Marco Della Fiore, Stefano Rescigno, Adele A. Vaccaro, Ugo |
| author_facet | Dalai, Marco Della Fiore, Stefano Rescigno, Adele A. Vaccaro, Ugo |
| contents | In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints.
By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $Θ(t n^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n +k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03491 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Efficient Algorithm for Group Testing with Runlength Constraints Dalai, Marco Della Fiore, Stefano Rescigno, Adele A. Vaccaro, Ugo Information Theory Data Structures and Algorithms 05D40 In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $Θ(t n^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n +k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1]. |
| title | An Efficient Algorithm for Group Testing with Runlength Constraints |
| topic | Information Theory Data Structures and Algorithms 05D40 |
| url | https://arxiv.org/abs/2409.03491 |