@inproceedings{baec5beced3244abadf7eddb536f8587,
title = "Scheduling Group Tests over Time",
abstract = "Group testing has been successful in minimizing the cost of testing a large batch of samples by pooling them together. In this work, we study the setting where samples arrive over time. Since not all samples are available at the same time, we incur a waiting cost in letting many samples accumulate. However, testing too soon leads to a large testing cost by missing the benefits of pooling a larger number of samples. We consider the problem of minimizing the combined objective of average wait time plus testing cost, and develop online algorithms that are provably competitive for a broad range of testing-cost functions. We also give a lower bound on the competitive ratio that no online algorithm can beat.",
keywords = "Online algorithm, competitive ratio, scheduling",
author = "Akhil Bhimaraju and Varshney, {Lav R.}",
note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 2022 IEEE International Symposium on Information Theory, ISIT 2022 ; Conference date: 26-06-2022 Through 01-07-2022",
year = "2022",
doi = "10.1109/ISIT50566.2022.9834434",
language = "English (US)",
series = "IEEE International Symposium on Information Theory - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "886--891",
booktitle = "2022 IEEE International Symposium on Information Theory, ISIT 2022",
address = "United States",
}