# Dynamic SAFFRON: Disease Control Over Time via Group Testing
## 3 Proposed Algorithms and Analysis
### Dynamic SAFFRON Based Group Testing Algorithm  
We propose and analyze a novel algorithm, which we coin as dynamic SAFFRON based group testing algorithm. It is inspired by the static group testing algorithm, SAFFRON, introduced in [41] and studied in [40] for partial detection. The static SAFFRON scheme-inspired algorithm presented in [40] is based on the idea of constructing binary test matrices for the groups of individuals that contain approximately one infected individual. Constructed SAFFRON scheme test matrices can be used to recover exactly one infected individual within the tested group, while also indicating whether there is zero or more than one infected individuals within the tested group if there is not exactly one infected individual. Here, we propose the novel dynamic SAFFRON-based group testing algorithm, where at each time instance \(t+1\), groups of size \(\lfloor(n-\gamma(t))/E[\lambda(t)]\rfloor\) are selected uniformly and randomly from the set of non-isolated individuals. For the \(\lambda(t)\) values that are close to their mean (Our numerical results suggest a concentration around the mean for \(\lambda(t)\). An in-depth concentration analysis can be the subject of future works. ), each of these groups has approximately one infected and non-isolated individual. By designing SAFFRON scheme-inspired binary test sub-matrices that are guaranteed to identify one infection from each group that has exactly one infection, we detect and isolate infections over time. For a selected group of individuals, the binary test sub-matrix is constructed as follows:  
* Let \(\eta\) denote the size of the selected individuals, i.e., \(\eta=\lfloor(n-\gamma(t))/E[\lambda(t)]\rfloor\). * First, \(\lceil\log(\eta)\rceil\) rows of the test sub-matrix are constructed where column vector that corresponds to column \(i\) is set to the binary representation of the number \(i-1\). * Then, remaining \(\lceil\log(\eta)\rceil\) rows of the test sub-matrix are constructed by concatenating the created sub-matrix in the previous step with the binary matrix where the value of each element is flipped, i.e., XORed with 1. By using this construction, it is guaranteed that, if there is exactly one infection within the tested individuals, there will be exactly \(\lceil\log(\eta)\rceil\) positive tests and the positive test indices will be the binary representation of \(i-1\) where the infected individual index is \(i\). If there is no infection, then all tests will be negative. In the case of more than one infection, strictly more than \(\lceil\log(\eta)\rceil\) tests will be positive. Thus, this construction guarantees the detection of a single infection within the selected group. In the following lemma, we characterize the expected number of detected infections at each time instance. When dynamic SAFFRON-based group testing algorithm is used, at each time instance \(t\geq 1\), in average  
\[\frac{T}{2}\log^{-1}\biggl{(}\frac{n-\gamma(t-1)}{E[\lambda(t-1)]}\biggr{)} \biggl{(}1-\frac{E[\lambda(t-1)]}{n-\gamma(t-1)}\biggr{)}^{\frac{n-\gamma(t-1)} {E[\lambda(t-1)]}-1} \tag{12}\]  
infections are detected and isolated. Proof. : We choose the group size as \(\frac{n-\gamma(t-1)}{E[\lambda(t-1)]}\) since there will be approximately one infected individual within each group when the groups are chosen uniformly randomly from the set of all non-isolated individuals. Since the testing capacity is \(T\) at each time instance, there will be  
\[\frac{T}{2}\log^{-1}\biggl{(}\frac{n-\gamma(t-1)}{E[\lambda(t-1)]}\biggr{)} \tag{13}\]  
such groups. Recall that the probability that a non-isolated individual is infected is \(\frac{E[\lambda(t-1)]}{n-\gamma(t-1)}\) due to the fact that dynamic SAFFRON-based group testing algorithm uniformly randomly selects the groups at each time instance and since the infection statistics are symmetric over individuals. Furthermore, the group size is inverse of this term.