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.

Original languageEnglish (US)
Title of host publication2022 IEEE International Symposium on Information Theory, ISIT 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages886-891
Number of pages6
ISBN (Electronic)9781665421591
DOIs
StatePublished - 2022
Event2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland
Duration: Jun 26 2022Jul 1 2022

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2022-June
ISSN (Print)2157-8095

Conference

Conference2022 IEEE International Symposium on Information Theory, ISIT 2022
Country/TerritoryFinland
CityEspoo
Period6/26/227/1/22

Keywords

  • Online algorithm
  • competitive ratio
  • scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Scheduling Group Tests over Time'. Together they form a unique fingerprint.

Cite this