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×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 c and any other k−1 columns, there exists a row where c has 1 and all the remaining k−1 columns have 0. These combinatorial structures were introduced by Agarwal et al. (2020), 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 Θ(tn2) for the construction of (k,n,d)-superimposed codes of length t=O(dklogn+k2logn). 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 Agarwal et al.

An efficient algorithm for group testing with runlength constraints

Della Fiore S.;Rescigno A. A.;Vaccaro U.
2025-01-01

Abstract

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×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 c and any other k−1 columns, there exists a row where c has 1 and all the remaining k−1 columns have 0. These combinatorial structures were introduced by Agarwal et al. (2020), 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 Θ(tn2) for the construction of (k,n,d)-superimposed codes of length t=O(dklogn+k2logn). 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 Agarwal et al.
2025
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4879931
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact