{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:46:55Z","timestamp":1760244415021,"version":"build-2065373602"},"reference-count":41,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T00:00:00Z","timestamp":1668988800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Group testing is an efficient algorithmic approach to the infection identification problem, based on mixing the test samples and testing the mixed samples instead of individually testing each sample. In this paper, we consider the dynamic infection spread model that is based on the discrete SIR model, which assumes the disease to be spread over time via infected and non-isolated individuals. In our system, the main objective is not to minimize the number of required tests to identify every infection, but instead, to utilize the available, given testing capacity T at each time instance to efficiently control the infection spread. We introduce and study a novel performance metric, which we coin as \u03f5-disease control time. This metric can be used to measure how fast a given algorithm can control the spread of a disease. We characterize the performance of the dynamic individual testing algorithm and introduce a novel dynamic SAFFRON-based group testing algorithm. We present theoretical results and implement the proposed algorithms to compare their performances.<\/jats:p>","DOI":"10.3390\/a15110437","type":"journal-article","created":{"date-parts":[[2022,11,21]],"date-time":"2022-11-21T04:13:36Z","timestamp":1669004016000},"page":"437","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dynamic SAFFRON: Disease Control Over Time via Group Testing"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5310-3834","authenticated-orcid":false,"given":"Batuhan","family":"Arasli","sequence":"first","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA"}]},{"given":"Sennur","family":"Ulukus","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742, USA"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1214\/aoms\/1177731363","article-title":"The Detection of Defective Members of Large Populations","volume":"14","author":"Dorfman","year":"1943","journal-title":"Ann. Math. Stat."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1002\/j.1538-7305.1959.tb03914.x","article-title":"Group Testing To Eliminate Efficiently All Defectives in a Binomial Sample","volume":"38","author":"Sobel","year":"1959","journal-title":"Bell Syst. Tech. J."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1080\/01621459.1972.10481257","article-title":"A Method for Detecting All Defective Members in a Population by Group Testing","volume":"67","author":"Hwang","year":"1972","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"662","DOI":"10.1016\/j.dam.2006.10.009","article-title":"Exploring the Missing Link Among d-Separable, d--Separable and d-Disjunct Matrices","volume":"155","author":"Chen","year":"2007","journal-title":"Discret. Appl. Math."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/0097-3165(94)90067-1","article-title":"On the Upper Bound of the Size of the R-Cover-Free Families","volume":"66","author":"Ruszinko","year":"1994","journal-title":"J. Comb. Theory Ser. A"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3019","DOI":"10.1109\/TIT.2014.2310477","article-title":"Non-Adaptive Group Testing: Explicit Bounds and Novel Algorithms","volume":"60","author":"Chan","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Baldassini, L., Johnson, O., and Aldridge, M. (2013, January 7\u201312). The Capacity of Adaptive Group Testing. Proceedings of the 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey.","DOI":"10.1109\/ISIT.2013.6620712"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"7522","DOI":"10.1109\/TIT.2016.2613870","article-title":"Nonadaptive Group Testing With Random Set of Defectives","volume":"62","author":"Mazumdar","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"3775","DOI":"10.1109\/TIT.2020.2970184","article-title":"Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach","volume":"66","author":"Scarlett","year":"2020","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1109\/TIT.2014.2375211","article-title":"Partition Information and its Transmission Over Boolean Multi-Access Channels","volume":"61","author":"Wu","year":"2015","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"992","DOI":"10.1109\/TSP.2017.2780053","article-title":"Optimal Nested Test Plan for Combinatorial Quantitative Group Testing","volume":"66","author":"Wang","year":"2018","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Du, D.Z., and Hwang, F.K. (1999). Combinatorial Group Testing and Its Applications, World Scientific. [2nd ed.].","DOI":"10.1142\/9789812798107"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"3671","DOI":"10.1109\/TIT.2014.2314472","article-title":"Group Testing Algorithms: Bounds and Simulations","volume":"60","author":"Aldridge","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"669","DOI":"10.11650\/twjm\/1500407300","article-title":"Sharper Bounds in Adaptive Group Testing","volume":"4","author":"Riccio","year":"2000","journal-title":"Taiwan. J. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1561\/0100000099","article-title":"Group Testing: An Information Theory Perspective","volume":"15","author":"Aldridge","year":"2019","journal-title":"Found. Trends Commun. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2113","DOI":"10.1109\/TIT.2017.2659619","article-title":"Efficient Algorithms for Noisy Group Testing","volume":"63","author":"Cai","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Karimi, E., Kazemi, F., Heidarzadeh, A., Narayanan, K.R., and Sprintson, A. (2019, January 24\u201327). Non-adaptive Quantitative Group Testing Using Irregular Sparse Graph Codes. Proceedings of the 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2019.8919896"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"5592","DOI":"10.1109\/TIT.2019.2902397","article-title":"On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing","volume":"65","author":"Inan","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1109\/TIT.2018.2861772","article-title":"Performance of Group Testing Algorithms with Near-Constant Tests Per Item","volume":"65","author":"Johnson","year":"2019","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Allemann, A. (2013). An Efficient Algorithm for Combinatorial Group Testing. Information Theory, Combinatorics, and Search Theory: In Memory of Rudolf Ahlswede, Springer.","DOI":"10.1007\/978-3-642-36899-8_29"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1880","DOI":"10.1109\/TIT.2011.2178156","article-title":"Boolean Compressed Sensing and Noisy Group Testing","volume":"58","author":"Atia","year":"2012","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Li, T., Chan, C.L., Huang, W., Kaced, T., and Jaggi, S. (July, January 29). Group Testing with Prior Statistics. Proceedings of the 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA.","DOI":"10.1109\/ISIT.2014.6875253"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Doger, M., and Ulukus, S. (2021, January 25\u201329). Group Testing with Non-identical Infection Probabilities. Proceedings of the 2021 XVII International Symposium \u201cProblems of Redundancy in Information and Control Systems\u201d (REDUNDANCY), Moscow, Russia.","DOI":"10.1109\/REDUNDANCY52534.2021.9606443"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1111\/j.1541-0420.2011.01674.x","article-title":"Group Testing for Case Identification with Correlated Responses","volume":"68","author":"Lendle","year":"2012","journal-title":"Biometrics"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"2170","DOI":"10.1109\/TNSE.2021.3081759","article-title":"Positively Correlated Samples Save Pooled Testing Costs","volume":"8","author":"Lin","year":"2021","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Nikolopoulos, P., Srinivasavaradhan, S.R., Guo, T., Fragouli, C., and Diggavi, S. (2021, January 13\u201315). Group Testing for Connected Communities. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, Virtual.","DOI":"10.1109\/ICC42927.2021.9500791"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Nikolopoulos, P., Srinivasavaradhan, S.R., Guo, T., Fragouli, C., and Diggavi, S. (2021, January 14\u201323). Group Testing for Overlapping Communities. Proceedings of the ICC 2021\u2014IEEE International Conference on Communications, Montreal, QC, Canada.","DOI":"10.1109\/ICC42927.2021.9500791"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Ahn, S., Chen, W.N., and Ozgur, A. (2021, January 12\u201320). Adaptive Group Testing on Networks with Community Structure. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9517888"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Arasli, B., and Ulukus, S. (2021, January 12\u201320). Graph and Cluster Formation Based Group Testing. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518128"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Nikpey, H., Kim, J., Chen, X., Sarkar, S., and Bidokhti, S.S. (2022). Group Testing with Correlation under Edge-Faulty Graphs. arXiv.","DOI":"10.1109\/ISIT50566.2022.9834777"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Idalino, T.B., and Moura, L. (2022). Structure-Aware Combinatorial Group Testing: A New Method for Pandemic Screening. International Workshop on Combinatorial Algorithms, Springer.","DOI":"10.1007\/978-3-031-06678-8_11"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Gonen, M., Langberg, M., and Sprintson, A. (2022). Group Testing on General Set-Systems. arXiv.","DOI":"10.1109\/ISIT50566.2022.9834789"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Karimi, E., Heidarzadeh, A., Narayanan, K.R., and Sprintson, A. (2022). Noisy Group Testing with Side Information. arXiv.","DOI":"10.1109\/IEEECONF56349.2022.10052078"},{"key":"ref_34","unstructured":"Acemoglu, D., Fallah, A., Giometto, A., Huttenlocher, D., Ozdaglar, A., Parise, F., and Pattathil, S. (2021). Optimal Adaptive Testing for Epidemic Control: Combining Molecular and Serology Tests. arXiv."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Srinivasavaradhan, S.R., Nikolopoulos, P., Fragouli, C., and Diggavi, S. (2021). Dynamic Group Testing to Control and Monitor Disease Progression in a Population. arXiv.","DOI":"10.1109\/ISIT50566.2022.9834823"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Srinivasavaradhan, S.R., Nikolopoulos, P., Fragouli, C., and Diggavi, S. (2021, January 12\u201320). An Entropy Reduction Approach to Continual Testing. Proceedings of the 2021 IEEE International Symposium on Information Theory (ISIT), Melbourne, Australia.","DOI":"10.1109\/ISIT45174.2021.9518188"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Doger, M., and Ulukus, S. (2022, January 9\u201311). Dynamical Dorfman Testing with Quarantine. Proceedings of the 56th Annual Conference on Information Sciences and Systems (CISS), Princeton, NJ, USA.","DOI":"10.1109\/CISS53076.2022.9751175"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Arasli, B., and Ulukus, S. (July, January 26). Group Testing with a Dynamic Infection Spread. Proceedings of the 2022 IEEE International Symposium on Information Theory (ISIT), Espoo, Finland.","DOI":"10.1109\/ISIT50566.2022.9834486"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1186\/s13662-020-02995-1","article-title":"Time-Continuous and Time-Discrete SIR Models Revisited: Theory and Applications","volume":"2020","author":"Wacker","year":"2020","journal-title":"Adv. Differ. Equ."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Aldridge, M. (2021, January 24\u201326). Pooled Testing to Isolate Infected Individuals. Proceedings of the 2021 55th Annual Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA.","DOI":"10.1109\/CISS50987.2021.9400313"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"4649","DOI":"10.1109\/TSP.2019.2929938","article-title":"SAFFRON: A Fast, Efficient, and Robust Framework for Group Testing Based on Sparse-Graph Codes","volume":"67","author":"Lee","year":"2019","journal-title":"IEEE Trans. Signal Process."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/11\/437\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:22:31Z","timestamp":1760145751000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/11\/437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,21]]},"references-count":41,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2022,11]]}},"alternative-id":["a15110437"],"URL":"https:\/\/doi.org\/10.3390\/a15110437","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,11,21]]}}}